Monday, August 29, 2011

Lispdown

As I read SICP, an idea arose in my mind to create a ()-less lisp. Its been done before, of course, but I was not really trying to redesign the language as I was attempting to remove visual clutter. To that end, I present:

 Lispdown. Its lisp, and its like markdown, get it?

This is still WIP, so if by some bizzare chance this gets into HN or reddit, bear with me. Its not done yet. In fact, its vaporware at this point. Just a concept. And a strawman at that :)

Alright, here we go:


  • Lispdown is to lisp as markdown is to html. Therefore, valid lisp is always valid lispdown. If you cannot use lispdown syntax, just use lisp's.
  •  Known forms are like begin-parens; add an end to finish them (Thanks ruby!)
  • A list is formed by any set of lines that has some sort of list begin marker(each line is an element), or a line separated by commas, or a part of a line in () or [] or {} separated by spaces or commas
  • A pair is formed using a colon to separate the two bits. this is only for readability as a space will do just fine.
  • I've yet to figure out how complex trees of function bodies can be reliably converted to lispdown without introducing python-style whitespace interpretation.
Update: There is now a Lispdown implementation

SICP: The first pass

I just finished my first pass through SICP. Well, "finished" might be a bit presumptuous because I skimmed through the latter chapters, but that was intentional: I couldn't wait to figure out what the book was "all about" -  especially the metacircular evaluator bits - that I HAD to skip ahead to find out if "the butler did it".

And boy did he do it! I havent read the book in detail at all, but already I see some core concepts that I had about programming being presented inside-out. For somebody who didn't grok polymorphism (for example) unless it was mentally transformed into vtable lookups, this feels like looking at a sculpture from the inside - while its being made. If that makes sense at all.

Let me try to explain. And before I go further, let me add: its not that its all functional programming (although the functional bits that blew my mind I've already blogged about) nor the lispy geekiness of it. Its more fundamental than that.

The method of imparting knowledge on programming that I've encountered to date has been additive: you're introduced to some basic concepts like assignment, looping etc; then taught how to string them together in expressions and statements; then string these into functions and procedures; and so forth. SICP seems subtractive in comparison: it states the problem and set out to decompose its solution into smaller bits till the basic statements are arrived upon, at which point some primitive "forms" (such as cond() are introduced for use). This would merely be bottom-up vs top-down if not for SICP showing along the way that programs and data are equivalent by creating a data store mechanism in pure functions, demonstrating data-driven programming (command pattern implemented using config file+ interface + n implementations for you java guys) using table lookups, shown how symbolic programming could be done with examples in calculus and circuitry, and finally demonstrating simulating a real programming system with stack frames, VM et al.

No doubt the internal reason is that functional programming works that way, but this is a powerful way of presenting programming for two reasons:
  1. It IS the right way to solve problems - especially large ones
  2. If you present it as the only way to do things - as the book does - new programmers wont know any worse :)
There is also a marked "peeling the onion" feel to the book - each chapter builds on the previous one. Here's the "storyline" that I've figured out to date:
  • Write programs by breaking them down into their constituent functions
  • Data can similarly be broken down using abstraction
  • Programs = data and vice versa
  • Programs may require state. Introducing state has its advantages and disadvantages
  • State => environment, and here's how you go about building one.
  • Now that you know how to build an environment, here's how you use it - to build a language evaluator.
  • Finally, here's how you'd do it a real world machine (I could be wrong on this one - I just read the heading "register based machine").
A emacs+clojure guy that I met over the weekend felt that the drawback with SICP was that there was no clear direction in the book as to how this knowledge can be applied. Maybe so, I'm not sure at this point.

When I bought the book I had a couple of goals in mind:
  • See what the book is all about given that it has all this fame
  • Learn Lisp in the process
The first one of these has been achieved, I think; and now that I've "got" it, I plan to go back and read the book in earnest, trying out the exercises along the way. The second goal, however, seems a bit misplaced. The book certainly uses lisp, but is not about lisp. I think I will still learn the kernel of lisp that's pure and universal to all its dialects - but that's about it. Now that I think about it, that's all the lisp I probably need :)

Having understood what the book is about, though, I think a reframing of goals is in order:
  • Understand program decomposition and data abstraction as espoused in the book. Try to use it in a non-trivial application
  • Try out exercises using Racket and post work to github (A la vru3dd)
  • Understand the language evaluator chapter. Try to use it on a toy language if that's possible
  • List how the concepts in this book are applicable in daily programming.

Monday, August 22, 2011

On Software Testing and the case for the Common Test Scenario Database


TL;DR


As a participant (and sometimes contributor of ideas) to Test Automation efforts (Strategy, tool selection and implementation), it has been my long-standing opinion that the true gains from automation can be achieved only when Test Scenarios (enshrined as exemplar test data) are a heavily reused resource across the organization. This page is an attempt to "arrive" at that opinion by progressively optimizing the software testing process.

I take the example of testing the hotel search feature and progressively optimize it through 4 stages to illustrate the value of each such optimization; and the value of shared test scenarios in particular.

What is Software testing?


Software Testing is the art and science of validating that a particular piece of software behaves as expected. Since most words in the previous sentence are loaded with meaning, I'll dissect it:
  • Art and science: Art because some of it is based on the skill of the tester and science because most bits are tractable into well-defined, repeatable procedures with predictable outcomes
  • Validating: This might involve the atomic step of input-process-output, or a sequence of many such atomic steps (typically known as "following a script"). Each such step (or steps) entails comparing an expected value (or more generally outcome) with a known one
  • Expected: This implies that there are some requirements that the software is supposed to meet which is an accumulation of the most important (or all) of the comparisons mentioned above.

A Concrete Example - Testing Hotel Search functionality

Any travel website has a hotel search functionality. You enter a destination, start and end dates and number of guests; and the website returns a list of hotels. Each hotel card has some details (name, location, address, picture, reviews, rating, description etc); and the list itself has some details (count, sort order, #pages, etc).

Notice also that there are some implicit inputs (eg: choice of POS, choice of currency) and some implicit outputs (eg: sort order).

To truly test this feature, you need to validate that:
  • The functionality is right:
    • The list is as expected (has the expected number of hotels which are in the expected order, paginated at the right place, etc)
    • Each hotel card is as expected (Has the name as expected, image shows up, description is correct, etc)
  • The display is right:
    • Visual characteristics for each data item is correct
    • No visual elements overlap
    • And so on
  • Adding the feature didn't break anything else:
    • tests on features that already exist pass
    • tests on features that are in-flight at the same time and targeted to the same release pass
  • The performance is within acceptable limits

Focusing on functional testing alone for a moment, we see that:
  • Each combination of values that we input produces a unique output; and
  • Each such output has details that need to be validated against expected values.

The universe of all things that need to be tested therefore is of the order:
             Number of input combinations  X  Size of output for each input combination
Now, for the hotel search scenario,
            Number of input combinations = Product of (Size of the set that an input belongs to) for all inputs.
And
            Size of each output = Size of result set details + Size of details for all hotel cards
Note: inputs include both implicit and explicit ones


Using the details mentioned above and ignoring the etc's for now,

Size of inputs for hotel search
Number of inputs = 2 implicit + 3 explicit = 5
Product of sizes
= Size of the set of destinations
X Size of the set of Possible Start dates (and invalid ones)
X Size of the set of Possible End dates (and invalid ones)
X Size of set of number of guests (subset of Integers)
X Size of set of POSs allowed (subset of integers)
X Size of set of Currencies allowed
 
= 50000 (assumed)
X 365 (assuming a year of allowed booking)
X 365 (assumed similarly)
X 4 (assumed to be max allowed guests per booking)
X 1 (assuming USPOS)
X 1 (assuming USD)
Size of each output
= 3 result set details + N x (7 hotel card details)
 
Where N = size of result set itself

If N = 100, the Test Universe = 50000 x 365 x 365 x 4 x 1 x 1 x (3 + 100 x 7) = 1E13 Tests
Onto this set of 1e13 Tests, we'll have to add the Regression, UI Validation and Performance Tests as well.


Sidebar for the mathematically inclined
 All testing can be considered validation of functions. Given an abstract function y = f(x), testing can be considered validation that for all x in X (the input set), there exists the expected y in Y (the output set)
The domain of the function represents the size of the input and the range of the function represents the size of the output. The Cartesian product is, therefore, the set of tests to be conducted to validate the function. 


Obviously, this is a lot of testing to do; and if we're actually able to do all of it, that would be Exhaustive Testing. Also obviously, anything larger than the simplest feature would quickly be intractable due to the combinatorial explosion of tests required; so we apply the "art and science" part and try to pare the problem down a bit. I'll focus on the functional testing here, but most of the concepts apply to UI validation and Performance as well.

Before we start, however, I'll define some factors to evaluate the efficacy of our optimization with:
  • The number of tests required to be run (or reduced as a result of the optimization)
  • The cost of running the tests (in terms of time, resources, $, etc)
  • The overall quality of the product is still within acceptable limits

Optimizing testing - Round 1: Scenario Based Testing

This optimization concept is very simple - reduce each set mentioned above to a representative subset. Each element of this subset would "stand for" or represent an entire class of values within the original set. A success or failure of the chosen value is deemed a success or failure of the entire class.

To continue the Hotel Search example, the inputs could be reduced to the following scenarios (for example):

Destinations
  • Top 10 destinations
  • 1 non-US destination
  • 3 destinations with "known issues" or special edge cases
Booking Dates
  • Last minute bookings (1 date in the next 3 days)
  • Planned bookings (4 dates in the next 2 quarters)
  • Peak date bookings (2 National holidays)
  • Weekend bookings (2 weekends in the next 2 months)
Guests

  •            4 is small enough a number to test all combos, but we could still pick a subset, say 1 and 4 only
With this, the input size drops to 13 x 9 x 2 = 234
And the test universe becomes 234 x (3 + 100 x 7 ) = 164,502

That's still a huge number, but 8 orders of magnitude less already! We could optimize this further by reducing the validation on the output values if we want to. Realistically, we can probably get away with checking 4 of the 7 details for the first 25 hotels; and checking the result set details just once throughout. So the test universe reduces to:
234 x ( 25 x 4) + 3 = 23,403

How has this impacted our evaluation factors?
  • The number of tests required to be run has obviously come down.
  • The cost of running each of the tests still remains the same; we haven't optimized that yet.
  • The resultant overall quality depends on the scenarios chosen. If we've chosen well; it should be within acceptable limits.

Note that there are more algorithmic ways of arriving at a subset of tests; Orthogonal Array testing to name one. I'll not elaborate on this further as the optimization is the same in principle - that of reducing the total number of tests required in validating a feature.

Similarly, on the regression testing side of the house, scenario-based reduction of tests can be done by carefully analyzing the areas that changed code is likely to impact; aka Impact Analysis.

Optimizing testing - Round 2: Automation

When you have many features similar to the one depicted above, scale effects come to bear:
  • The total number of tests to be run is still a large overall number
  • The cost of regression is a constant despite reducing the regression test suite using impact analysis.

The optimization to counter this is conceptually simple - relegate repeatable tests to a machine so that human cycles can be spent on the unique ones. This is easier said than done in practice; and the quickest way to get started is - surprisingly similar to BDD precepts - Outside In. That is, start at the outermost layer and automate tests at that layer. Work gradually inwards; or even not at all. Automating regression alone can have significant benefits.

One of the biggest issues with automation, however, is that you miss out on the human ingenuity bit. Scripts WILL break if data changes over time, so environments have to be stable; something that the human tester would easily sidestep by validating "outside the box" that the changed data is indeed still valid.

To continue with the Hotel Search example, assuming both the human and the machine take the same time for a test, the gain in human cycles due to various levels of automation are:

Feature
Manual Tests
Human cycles saved with 10% automation
25%
50%
75%
Hotel Search
23403
23404 * .1 = 2340.4
23404 * .25 = 5851
23404 * .5 = 11702
23404 * .75 = 17553.0

Reviewing our factors again, we see that with this additional optimization,
  • The number of tests required to be run by humans has come down again and the tests run by machines can be run repeatably so.
  • The cost of running each of the tests has reduced, but the cost of maintaining test environments went up as both manual and automated environments have to be kept running.
  • The resultant overall quality still depends on the scenarios chosen and our trust in our automated tests. If we've chosen well and trust our scripts; it should still be within the same acceptable limits.

Optimizing testing - Round 3: Component based testing

The cost of maintaining test environments mentioned above is typically the tip of the iceberg. All testing espoused to this point has been strictly end-to-end, ie, the environment has been a live one from the UI all the way to the database (or back-end). There is a non-trivial cost associated with maintaining these environments; and a collateral cost of maintaining scripts (or known data for use by the scripts) as those environments change. Additionally, some kinds of testing may not be possible in live environments. Booking scenarios are typically such tests - contractual obligations or the cost of test bookings may deter such tests from being done in a large scale or at all.

In addition, end-to-end testing forces the entire organization into a train wreck of dependencies. Since all testing is done from the UI, all code must be built and integrated before ANY testing can start. This not only delays testing, it also puts pressure on changes to the inner layers of the application - that code has to be completed WAY IN ADVANCE of the UI code, but cannot validate their output until the UI is done.
Component testing attempts to fix these issues by testing each component
at ITS interface, not at the final user interface. That way, the owners of that component know for sure that they produce valid output for given input; a large live environment need not be maintained; and the validation of a test scenario is spread across multiple component tests which together comprise the larger validation.

Component testing almost always predicates the mocking of dependent components because the cost gains are not realized otherwise. That is, if A -> B -> C is a string of components involved in a particular test scenario, C must be mocked out to test B and B must be mocked out to test A; otherwise we've taken on the additional job of maintaining a separate instances of A,B and C solely for component testing purposes, thereby increasing cost of maintaining environments more than without it.

Component testing also typically requires some means of creating mock data - manual means will not suffice; especially if the request-response payloads are huge object graphs.

The choice, adoption and usage of an organization-wide mocking framework is therefore a non-trivial task and I will not go into the details of how to achieve this. I will, however, analyze the impact of adopting such component testing on the evaluation factors mentioned above.

To continue the Hotel Search example, a hotel search typically involves a string of internal components:
                                                               |------------> GDS
UI -> Business  -> Business  -> Business  ->    Back End-------|------------> CRS1
Dispatcher        Facade     Logic Executor  Abstraction Layer
                                                               |------------> CRS2
(Some details may be missing; sorry. I'm trying to make a larger point here).

Let's take the following Test Scenario:

Input
Expected Output
Top Destination (LAS), Weekend (start: next Friday, ret: next sun), 1 guest
  • 1st page has 25 hotels
  • 1st hotel is Caeasar's Palace @ $100
  • 2nd hotel is MGM @ $125
  • …and so on
…and break it into component tests:


Component
Given a test script that provides this input
..should provide this output
..using this mock data
UI Layer
LAX, Next fri, Next Sun, 1 guest
  • 1st page has 25 hotels
  • 1st hotel is Caeasar's Palace @ $100
  • 2nd hotel is MGM @ $125
  • …and so on
  • Business Dispatcher response containing the 25 hotels
Business Dispatcher/ Facade
LAX, mm/dd/yyyy,mm/dd/yyyy,1
+ other Dispatcher required params
Arraylist of Business Layer objects
  • Executor response containing the 25 hotels
Business Logic Executor
LAX, mm/dd/yyyy,mm/dd/yyyy,1
+ other Executor required params
Arraylist of Executor-specific objects
  • LAX-to-internal-location-object response
  • Back end Abstraction Layer responses
Back end Abstraction Layer
LAX, mm/dd/yyyy,mm/dd/yyyy,1
+ other Back end required params
Arraylist of Back end Abstraction Layer objects
  • Back end-specific responses (1 per link)

We'd have to do a similar exercise for each such scenario identified before as required, but if we did, the impact on the factors would be:
  • The number of tests required to be run by humans has come down again and the tests run by machines can be run with lesser resources.
  • The cost of running each of the tests has reduced; so has the cost of maintaining test environments as live environments no longer need be maintained.
  • The resultant overall quality now depends largely on the fidelity with which the end-to-end scenarios have been mapped to component tests. If there is a high correlation between the two, overall quality should still remain within the original acceptable limits.

This last is not easy to do for various reasons:
  • There needs to be a coherent effort to ensure scenarios matchup between components; else component owners could define their sphere of influence differently from the scenarios deemed organizationally important.
  • The larger the size of mock data to be created, the more difficult it is to create it with high fidelity. Shortcuts such as record-replay mechanisms might help, but only if they've been sanitized to remove volatile data and then made generic to match the expected scenarios.
  • Ownership is shared; so division of labor should be clearly defined via policy. For example, each component owner should be responsible for her front end, ie, provide mock data and a set of regression test scripts to his clients; she can therefore rely on her dependents to do the same. Without such a policy, key pieces of the puzzle will be missing and the overall quality will suffer.

Optimizing testing - Round 4: Common Test Scenario Database

These issues with implementation of component testing may even lead to a regression back to manual testing. The crux of the problem is that the cohesive force of the end-to-end test is lost in component testing very easily.

The central idea with the common test scenario database is retain the benefits of component testing while bringing back that cohesion via data: we need to ensure that test data that is distributed across the various component test scripts still have the same tie-in to the original scenario. That way, every component owner in a particular scenario refers to the same scenario using the same language. While we're at it, it would also be beneficial to change the mock data in two ways:
  • Replace significant pieces of live data with values that stand for the class of test data that we will use in the specific scenario. E.g., the destination data item when used in a scenario where it represents a top destination could be given the canonical name "Top Dest1". Alternatively - assuming this is clearly understood company-wide - a real value can be used as a canonical one ; eg, in this case "Las Vegas" could stand for top destination; but then it shouldn't be used in any other scenario.
  • Clear out any recorded values from the mock data so only known values remain. This eliminates side effects from remnant data but requires a higher degree of discipline.

The larger change would be to introduce full-fledged exemplar data sets for application domain concepts that cannot be confused with live data, but clearly denote the exact scenario in which they can be used; and use policy to drive adoption of these exemplar data sets as the mock data backbone.

To continue on the hotel search example, the first step would be to define the following exemplar data:

Concept
Exemplar Data
Comment
Top Destination
LAS

Regular Destination
USDEST1

Special Destination
Acme Cozumel
Added "Acme" to Destination to call out that this is a test value
Next Week Friday
(Computed Value)
Mock data framework should be able to generate such values and respond appropriately
Hotel Chain
Acme Hotels LLC

Hotel
Grand Acme Ritz Chicago

Top Hotel @ Top Destination
Acme Hotel and Casino


The component test from before can then be rewritten like so:

Component
Given a test script that provides this input
..should provide this output
..using this mock data
Web-wl
LAS, Next fri, Next Sun, 1 guest
  • 1st page has 25 hotels
  • 1st hotel is Acme Hotel & Casino @ $100
  • 2nd hotel is Acme MGM @ $125
  • …and so on
  • TBS response containing the 25 hotels
    (Note: other hosts required to bring wl up ignored for now)
TBS/Plugin
LAS, mm/dd/yyyy,mm/dd/yyyy,1
+ other TBS required params
Arraylist of BookProduct objects
  • HSE response containing the 25 hotels
HSE
LAS, mm/dd/yyyy,mm/dd/yyyy,1
+ other HSE required params
Arraylist of objects
  • Market/Markup response
  • Supplier Link responses
SL Host(s)
LAS, mm/dd/yyyy,mm/dd/yyyy,1
+ other Supplier Link required params
Arraylist of objects
  • SL-specific responses (1 per link)

More importantly, when a second scenario has to be mapped to component tests, the exemplar data table above should be checked to see if the concepts in that scenario already exist, and if so they should be reused.

So, to convert the following scenario:

Input
Expected Output
Top Destination , Peak Weekend, 4 guest
  • 1st page has 25 hotels
  • 1st hotel is Acme Hotel & Casino @ $100
  • 2nd hotel is Acme MGM @ $125
  • …and so on

...into component tests, the following data items will have to be reused:
  • Top Destination (LAS)
  • Top Hotels (Acme Hotel & Casino, Acme MGM)
…and some new data items will have to be added:
  • Peak Weekend (Thanksgiving dates, for eg)

…which will further be reused when automating the scenario:

Input
Expected Output
Top Packaging Destination , Peak Weekend, n guests
  • Acme Mexico Dest1
  • Labor Day Weekend dates
  • 2 guests
  • 1st page has 25 hotels
  • 1st hotel is Acme Cozumel Resort1 @ $100
  • 2nd hotel is Acme Cozumel Resort2 @ $125
  • …and so on
.. Which will further require new data items to be created, and so on.

When a new feature is added, say separate pricing for children or prepaid hotel rooms, that's the time for a completely new set of hotel chains and hotels to be created.
Over time, this practice of reusing test scenarios results in the creation of the Test Scenario Database which becomes the lingua franca across the organization when talking about Quality issues.

Let's see how our measuring factors score with this optimization:
  • The number of tests required to be run by humans hasn't changed since the last round.
  • The cost of running each of the tests remains as before. If there were any collateral increase in costs of using live environments due to inability to trust component tests, that is removed however.
  • The resultant overall quality still depends largely on the fidelity with which the end-to-end scenarios have been mapped to component tests; but there's a direct correlation possible because the organization now has the "common language" of the scenarios enshrined in the test data. This is the killer quality of the common scenario database.

Notes on implementation


  • Just as with automation, creating a Test Scenario Database is easier said than done. Policy from "up top" will certainly help; but a grassroots approach is also possible because the database can be built one scenario at a time. It does require a few enthusiastic converts, but some key component owners being convinced will create the kernel of good, reusable (and reused) test scenarios which can then be supported via policy.Once their use is common, network effects will take care of their popularity.
  • The Quality Organization should own the Test Scenario database and gate-keep use and reuse. Developers may create test scenarios, but should get approval from Q.
  • Component owners should be responsible for their component and their front end interface; and expect their dependents to do the same. That way they have the responsibility towards their clients and expect the same from their dependent servers.


Todo

  • Create a Test Scenario database tie-in for the Robot Framework

Tuesday, August 09, 2011

Dynamic Logic: The good parts

A while ago I'd bought a book on Dynamic Logic on a whim. I came to know of the existence of such a field through a dismissive comment from Spolsky (or was it Yegge?) and apparently thought it worth my money to see if it was indeed to be dismissed thusly.

The book lay unread in my book case in India for a few years until my wife brought it by mistake to Chicago, where it again lay unread. Finally as I returned to India, I put the book in the "throw/drop into building library" pile, but just couldn't do it because it was after all a book.

So while my favorite books took the slow way home via ship, this book that I didn't really care much for travelled with me and became my reading material for the initial days in India when I'd not yet unpacked and yet needed some material to read on my daily commute.

So what's dynamic logic all about? Turns out its a mathematical way of proving programs do what they're supposed to. The initial bit of the book is a refresher on the set and logic theory required to digest the rest of it, which is a whole lot of "here's how to prove that you can prove things about programs". I'm paraphrasing, obviously, but clearly it was a "How" book, not a "Why" book; which was fine because it was intended to be a textbook for Philosophy majors and CS PhDs apparently.

Since I was not reading it for those reasons, however, I applied Penrose's advice (cf Emperor's New Mind) of simply glossing over any math that I didn't understand and tried to glean the "Why" from the pile of "How". Here's what emerged:

  • Dynamic Logic harbors the hope of describing programs in terms of pure logic so that you can make assertions about the outcome of running them. I'm not sure how you could do that to real world apps.
  • However, the concept of attaching a first-order (or higher) predicate to a program so that the tuple (program, fact/predicate/rule) represents the duo of what the program is and what its execution means seems useful, especially in the kind of code analysis scenarios I'm interested in. It should be tempered with a suitable dose of allowance for leaky abstractions, however. Fuzzy logic maybe? I don't know.
  • Nowhere in the book did I see any attempt at interpreting anything larger than one program. And its a book of about 600-700 pages.
  • Towards the end was a section on Temporal Logic. This technique attempts to understand the dynamic nature of running processes by asserting their state at a particular point in time. This is markedly different from the Dynamic Logic method of analyzing the outcome of the finished process and is therefore suited to long (or always) running processes like Operating systems. To me this looked like an interesting way of modeling debugging.
I'm sure I'm missing a lot of the great parts in Dynamic Logic because of my engineering bias, but I'll take the program+fact tuple concept away with me.

Requiem for a capability-based UI framework

I recently bought a macbook and was somewhat surprised to be back in a world where you had to pay for software :). Needing an outliner and not wanting to buy one, I thought I'd build one myself; using that as an experience to try out Fantom - a language that I've been meaning to try out for some time now.

Fantom comes with its own UI toolkit - FWT - which is a wrap on the SWT framework; only since extended to handle Javascript output as well. Promising enough; so I set out to build my simple outliner. A few hours of copying from samples and looking up the API later, I had a basic tree displayed on my screen. That's when I hit the snag.

You see, FWT's Tree Control didnt allow editing the nodes, neither did its model. I didnt ask the Fantom community, but it looked like you had to build it. An outliner without an editable tree seemed pointless, so I stopped there.

More importantly, I stopped because building an editable tree control in FWT was at least one order of magnitude more difficult. Merely on my requirement for a directly editable tree control, the effort to build my app went from "Using FWT to quickly building an outliner" to "Figuring out how SWT does editable Tree Controls, then figuring out how the authors of FWT have chosen to interact with SWT ie, Fantom's FFI, making changes that fit with the rest of the FWT model/control concepts and optionally making sure it works on Javascript (if I wanted it to be a true FWT control)". From all the passive lurking I've done on the Fantom community, it's probable I'm a bit off in the level of effort and there's a better way than the doomsday scenario I've painted here, but my point is this:


  • Most UI frameworks are dichotomies: there are the standard controls and the custom ones. 
  • Standard ones are easy to use, custom ones are not. 
  • In fact the custom ones are not easy to build either because the UI framework typically provide a blank slate for display (aka the canvas) and a generic message pump (aka the event loop+event object hierarchy). Everything else is up to you-who-isnt-happy-with-the-standard-controls.
  • The upside: if the framework is popular/active, more custom ones become standard ones over time. So if you're willing to play the waiting game, you'll get what you want.
  • The downside: If you dont want to wait, or have the really cool interaction design that needs all-custom controls, you're down to building them from scratch yourself.
Aside: I measure UI framework maturity in terms of how close/far off it is from a standard editable tree+table control. All UI frameworks inevitably gravitate towards this control (because you WILL finally need one) and when you do, you're doing it because your customers/users need it - ergo you have reached maturity. I think I'll call this Vinod's UI Law - A UI framework is mature when it has a standard editable tree+table control :)

Capabilities
Anyhoo, the point of this post: Why can't UI frameworks be oriented more towards what the controls DO instead of what they ARE? Imagine a framework that describes its controls in terms of their attributes or capabilities; things like : 
  • Editable/Display Only, 
  • Aggregated (ie, represents a list of data elements at once), 
  • Drag/droppable, 
  • Executes a command, 
  • Selects a value (single/multi), 
  • Reads in text
Each of these capabilities brings to mind the set of operations that a control that has that capability should support. For example, an editable control should have a model.edit() and a view.onEdit().

The implementations of each of these operations are obviously dependent on the specific control, but the benefit of having controls defined this way makes them both easy to implement and replace/switch from. It also allows a "degrade path" for presenting controls. In a device with reduced resources, it might make sense to instantiate the simpler parent control that the much more capable child because they support the same interface.

Painting

Now onto the actual painting of the control itself. The common strategy by all frameworks is to provide a Canvas and a set of tools to draw on it. You can repaint() when you're done with the changes from recent events, and your control displays in the updated state. Can this be improved at all?

What if the painting of the control changes from a list of procedural steps to a description of the the final display? Eg, a button that was painted by drawing a rectangle, and then drawing some text over that rectangle would now be described as a "rectangle containing text blah". That way, low level APIs (think GL, SWT) would have to only be provided with the parsed form of the description as a set of draw instructions to execute.
Con: All this parsing will come at a price on performance

We don't need to stop there, however. What if version 0 of the control's entire display was an image, and each of its possible states were also images that are replaced (suitably scaled, etc) like sprites? We could even imagine the version 0 being retained to allow graceful degradation of the UI (in older versions of the device, for eg) similar to the Alt text in HTML. Another approach that the low-level API could take is to treat the description as the spec for an image map with regions that can be interacted with.

This still doesn't completely alleviate the "order of magnitude" problem I mentioned above. Somebody still has to write the low level API to translate the description of the control into actual display logic. However, it does make custom UI controls first class citizens, and it does so in an implementation-neutral way. As long as somebody writes a low level API that can parse the control's description, it can be displayed in a device.

Eventing
Onto Eventing. Eventing frameworks continue the dichotomy of standard and custom. Most (all?) UI eventing frameworks assume a standard set of events that are typically tied to the physical input and output peripherals that the system uses and provide direct support for their events. This is obviously useful in getting up-and-running quickly, but adding any new events is quickly relegated to the vendor providing the new input/output device/peripheral. Can this be improved? Consider the following contrasting ways of looking at the same event:

  • "Key pressed" vs "character input"
  • "Many keys pressed, followed by loss of focus" vs "string entered"
  • "value entered in day textbox within set containing month and year textboxes" vs "Calendar control's date region clicked" vs "Day part of day chosen"
  • "Save Button clicked" vs "Save Command chosen"
  • "Three finger salute" vs "Lock screen command chosen"
I've deliberately picked some known examples to highlight that we're already halfway there. We DO have "high level" events already in most frameworks. My suggestion is to elevate them to the only ones available via the API and provide a language for the compounding of low level (physical) events into such high level ones.
This way, the API is no longer tied to the specific capabilities and/or peripherals attached to the device in use.

So there you have it, my requiem for a capability-based UI framework:
  1. Describe controls in terms of what they do. The allowed set of operations on a control should be governed by a set of interfaces/mixins that its defined to follow
    1. Extending a control by adding a new interface/mixin should bring in default behavior of that capability
  2. Describe - not define - how the control should be painted. Let the implementation ABI know merely how to translate the description into the specific display
  3. Define the eventing API in terms or High level events and define a language to compound low level events into the high level ones. 

SICP: The beginning

Partly inspired by the recent HN survey on SICP and the related post about MIT moving away from it I looked for SICP at Sapna Book Stall the other day.

I was pleasantly surprised to find it at all considering the wall of computer books were decidedly career oriented; and more so because it was the indian edition that was priced at Rs.595 :)

So I've actually started reading it on my commute - and I'm beginning to see a glimmer of the difference to the approach that this book (and possibly Lisp) has to programming compared to other texts. Its speaking the same language, but not quite in the same way; not to mention that it manages to slip in some really cool things without even so much as a by-your-leave. Case in point: Page 21 has this exercise:
Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:
 (define (a-plus-abs-b a b) ( (if (> b 0) + -) a b )) 
Right there, without any ceremony is a statement returning a function - and an operator at that! And answering why is considered an exercise to the reader - nice :).

Hopefully, I'll be able to keep the steam up in reading this book; and possibly even trying the exercises out.

Bonus: A footnote had this gem from Alan Perlis: Syntactic Sugar causes cancer of the semicolon :)

Thursday, August 04, 2011

New paradigms in wiring code emerging

It seems to me that ideas happen at the same time to many people. I've been thinking of ways of wiring code other than stacking 'em one after the other, and I find Coplien talking about DCI (although in fairness his ideas are a bit old - I just discovered them now), and today this:

The title's a bit dramatic, and the content seems original but is probably not entirely new(Google and ACM search pending).

What excites me, however, is:
  • Wiring code is being treated as a first-class problem
  • Solutions are recognizing the problems of being in Nounland (thanks Yegge), but not knee-jerking into functionville entirely. Solutions are emerging that are somewhere between, where the common coder lives!