Naive parsing techniques – part I

In this post, I’m considering a design for a simple tool that could help doing the following:

• Repackaging classes; this will involve replacing package and import declarations
• Validating class dependencies
• Generating code and TODO annotations from an incomplete specification
• Tracking high level aspects of system architecture by extracting relevant data from program code

Looking at the above, we’d surely agree that some kind of API would be required to take care of source analysis. This is where naive parsing comes in play.

If we needed an API to help resolve the above tasks unambiguously, we would also need to parse the source code reliably. However, writing parsers is overkill. In fact, just setting up and integrating with a parser might be quite a stretch.

Instead of going the full stretch, I’m proposing to write a naive parsing library. This will consist in several utility methods allowing to scan source files, detect relevant code fragments with a high (not absolute) degree of confidence and add/modify source files.

Why naive parsing?

I’ve already given half of the answer: parsing is expensive. Using naive parsing functions will allow my reusing the same techniques across similar languages. We’ll not only be saving time preparing the parsing facilities – we’ll actually save time every time we need to write another utility. That’s where ‘naive’ comes in play.

Most parsers somehow relate to the way we model language. However, there are strong smells indicating that parsers do not quite interpret text as we do:

• Classic parsers do not usually integrate error correction. When reading text, we are performing a mix of interpretation and error correction
• Given correct input, however complex, a classic parser will resolve that input into a parse tree of arbitrary depth and breadth. When reading text, we can easily overload when a sentence becomes too long and too complex.

Parsers, then, provide fail-fast, scalable solutions. Scalability is definitely a quality, but comes at a cost – naive parsing consists in simple rules that are easy to come up things, whereas writing scalable parsing rules is an art. Fail-fast may or may not be a quality depending on the context. For example, we might want our utilities to correct simple mistakes, even if that means introducing another mistake from time to time. After all, our code will eventually get either interpreted or compiled, so we only want to make sure that our automations generate an overall reduction in development cost.

Isn’t 100% reliability a paramount requirement?

Yes, but not in the parser used by our utilities. We need %100 reliability in the final product – what our utilities are helping us build – in contrast, we only need our utilities to save more time than they cost. In this particular scenario (considered the originally suggested applications), three strategies will be used to achieve correct results using only a ‘mostly accurate’ parser.

1. Simple, readable code. Simple, readable code is advocated everywhere. This suggests that parsers that allow very complex code – code that humans find hard or impossible to read – are too powerful. In short, we’ll agree to rewrite some of the code that the parser cannot read wherever this arguably increases the readability, simplicity and maintainability of the source.
   
2. Semantic separation. As we’ll see later, a naive parser often fails to analyze correctly code that uses semantic overlaps. Semantic overlaps don’t really promote simple code, and need rarely occur in program code, although classic parsers often rely on very limited semantic separation – for example very limited number of language keywords.
3. Patches. We will allow defining patches that determine project specific exceptions to the parsing process. This will be provided as an ultimate measure, mostly used to deal with legacy code that cannot be modified.

That’s all folks

Here’s a plan. Yes, I do have something concrete in mind, but if you read this post, I’ll be delighted to get feedback and hear that this has inspired ideas that have nothing to do with what I envision

The F* meta-pattern

F***, I can’t find the code that froggles the wizzles.

If you have ever worked on a delivery team, you know how hard it can be to map the user perspective leading to bugs being raised to actual application code.

Feature architectures emphasize feature separation over layering, and may be especially suitable for front-end development and integration software.

Classic architectures emphasize layering over component separation. A paramount example is the MVC meta-pattern, where applications are divided into model, view and control layers, and a component hierarchy is designed across application layers. MVC has imposed itself in application development – so much so that a colleague recently suggested to me that MVC is no more than a simple warning – don’t shoot yourself in the head; in the meantime, MVC relies on an over-arching principle: separation. In software architecture, separation determines what you can, and cannot do. If MVC is good for writing applications, surely MVC will promote uses that are common to an application product’s life cycle. Granted, let’s review the situation:

• MVC makes it easy to entirely re-implement a complete layer of your application: you could be re-writing your Swing UI in OpenGL, or re-use your data model using a web front-end. Or even reuse your view and model and create a new product following a different business logic – as encapsulated into your controller.
• MVC lets you hire specialists to write the separate layers of your application – a GUI wizard may be writing the UI while an XML wizard develops the model.
• Given an existing model, MVC could help you design new ways of interacting with this model.

Now, here’s a couple of things that an MVC architecture won’t help you with:

• MVC won’t help you introduce new features in your application – since features typically cut across model, view and control, the more features you add, the more time it takes to integrate scattered elements of functionality within existing application layers.
• MVC won’t help you fix bugs – while users and testers associate defects to application features – elements of perceived functionality – MVC separation promotes feature obfuscation (feature semantics differ across layers) and require iterating investigations across layers, typically starting from the UI.

I have never met a developer involved in replacing an application layer wholesale; further, while assigning specialists to writing separate application layers may ensure that each layer is well designed, this also increases the chances that layers do not interact correctly and will often lead to over-design and creeping featurism within each application layer – leading to unused potential. Separation? Yes. Layering?

Agile resolves some of the problems associated with layered architectures – in Agile, developers focus on delivering value by completing the user stories that express a customer’s actual needs. Pair programming and pair swapping also ensure that Agile developers are generalizing specialists. While developers still juggle between application layers on a daily basis, communication failures – both socially, within the team, and technically, within the product – are much reduced and bug counts dwindle. Agile teams may even be more able to process change requests reactively and effectively: a generalizing specialist will be able to investigate a solution across layers, where a team of specialists may be involved in investigating a bug or change request, with all the communication overheads that this may entail.

Features, then…

Where MVC stands for model, view and controller, the F* meta-pattern primarily resolves software architecture as a collection of features. In other words, instead of packaging your application using, view model and controller root packages, you create a new package for each feature, and commit to primarily developing each feature using a self contained source bundle. MVC does not forbid identifying features as an after-thought (see [ref]), it just makes it harder; similarly, F* does not specify that you should not separate view, model and controller – it does make it harder, however. Like Test Driven Development, F* represents a significant paradigm shift in the way we model and develop software. In short, F* determines increasingly strong requirements with regard to feature separation:

1. (The source code for) any given feature should be physically separate from any other feature.
2. Erasing source for a feature should not result in a broken build or a broken application.
3. Erasing or disabling a feature should not result in other features (dependents) being disabled unless the dependencies are conceptually integer.
4. A developer needs not access the source code for a feature in order to integrate with that feature.

Given increasingly stringent requirements, F* boasts increasingly attractive benefits

1. Developing a new feature requires little knowledge of existing features; further, existing features provide self-contained, integrated examples to any developer learning the code-base; further, developers can work in parallel with little risk of causing merge conflicts or stalling on another developer’s critical path. Surprisingly, we have a methodology suggestively capable of satisfying software managers brooding over Brooke’s Mythical Man Month.
2. Features are developed better and faster. This will be especially true in an agile environment where developers complete Stories. Often, a single feature will match a unique story and keeping all the code for a story in the same place means that developers are more able to focus on completing the story and less likely to break code implementing another story.
3. Maintaining existing features requires little analysis. Where all the code for a given feature is gathered within one or a few classes sitting in the same package, debugging and analyzing such code can be achieved in finite time, without the risk of meandering within a large code-base – in contrast, fixing bugs across complex, layered architectures evaluates to systematic investigations that only discipline, tenacity and perseverance can resolve.
4. Given an appropriate infrastructure, decentralized projects can be conducted with reduced liabilities.
5. Remote developers can contribute either commercial or non commercial value increments on an ad-hoc basis.

F* prerequisites

F* requires a paradigm shift in the way we develop our code; I am currently experimenting with the development of ee-xml, an open source XML editor. First, let’s cover a couple of prerequisites to developing using F* in front-end development:

• F* requires a widget library. If this seems contradictory, consider the fact that MVC applications also require GUI libraries. Right or wrong, I tend to perceive the emergence of reusable GUI library components as an avatar of the MVC meta-pattern. I also believe that MVC fails to support application developers in inverse proportion of the size of a software company – the smaller a company, the least likely that company will be to benefit wholesale application layer re-writings. F* does not replace a GUI library, it requires (and benefits from) retrofitting view layer elements within features.
• F* requires a simple data model encompassing your domain logic. If this seems contradictory, take the case of PureMVC. Value objects typically implement domain logic, while Proxies realise an application’s business logic. F* requires (and benefits from) retrofitting your business logic within features.

For ee-xml, I use the Swing library and an object oriented XML library.

Developing using F*

In a classic, layered architecture, code is designed and written from each component’s point of view. In F*, code is written from the feature’s point of view. To this extent, F*, like procedural programming, is easier to understand than patterns like MVC. Even though, F* is no less object oriented than MVC.

F* is a separation driven architecture. Features are written as self contained bundles of resources; notifications are used to integrate features by enforcing their conceptual dependencies. Here is a recipe for designing a feature:

1. Consider your feature in isolation – granted that a feature may access shared resources, assume that you have already collected references to such resources. Resources are typically represented as fields within a feature class.
2. Resolve the interaction entailed by the given feature.
3. Register to receive notifications. in F*, notifications typically convey references to view and model objects. You receive and generate notifications because you wish to share resources with other features.
4. Provide code instantiating all resources that your feature needs create.

In a simple example, we have a first feature dedicating to opening an application’s main window; a second feature is tasked with allowing the user to open an auxiliary window from an existing frame. In this case, we will analyze the second feature:

1. We determine that our feature requires an existing frame and a menu, and will allow the user to select a menu item.
2. Upon activation of the menu item, we create a new window and issue a notification.
3. We register for receiving a notification when a new window is created. Discovering which notifications are available, and what these notifications mean, is best done at runtime assuming notification traces, but could also be done statically by referring to the list of available notifications.
4. Upon receiving a reference to a newly created window, we need to ensure that such window will be equipped with a menu bar, menu and suitable menu item. We then register to receive an event when the menu item is selected.

I have chosen a simple example to clarify our recipe for writing a feature. In a real world context, a feature will typically map a user story and may be more complex. Within the development of ee-xml, opening a file represents a feature. This entails accessing I/O resources as well as creating fairly complex view elements.

Given the above example the typical life cycle of a typical application feature is as follows:

1. The feature is instantiated by a registry. The registry maintains a list to all currently available features and will, in simple cases, instantiates all features on start-up. At this stage, the feature is neither initialized nor available.
2. Upon instantiation, a feature registers to receive notifications. In front-end development notifications will often be issued to signal that a UI resource has been made available.
3. Upon receiving a notification, a feature will initialize. The same feature may initialize several times (in the above example, the feature initializes every time a new window is created). Initialization consists in adding widgets or other UI components to the application and listening to events issued by such components.
4. Upon processing the event(s) the feature is listening for, the interaction is resolved and further notifications may be issued.

Ready to rock?

Back in 2000, I embarked on a long journey aiming at reducing the loss of momentum associated with layered architectures; I wrote several IDEs, eventually, lifting my limit from managing and maintaining just 50 to 3000 classes or more as a solo developer.

Any growing application entails an increase in physical and logical complexity; the Antegram IDE helped me reduce the perceived complexity of my applications. What Antegram achieves with the user interface, F* promises to achieve using adequate separation, and once again, I’m ready to rock, putting aside natural skepticism.

F* is a meta-pattern; it can be instantiated using several languages and implemented in various ways, following increasingly strict requirements, and providing increasingly strong benefits. I am currently finalising a compile safe F* framework in Java and writing the first open source F* application.

Don’t shoot yourself in the head.

Programming Using State Transitions

Actions Pass, State Remains

Many widely used languages today are imperative. Essentially, most code written using those languages can be reduced to statements, such as:

System.out.println("Hello World");

I had the idea of programming using state transitions while trying to find reasonable ways to formally encourage writing simple, readable code. There are two drawbacks of classic imperative programming that pointedly led me to state transitions:

• Complex control structures – imperative programming often results in lengthy method bodies – so called ‘bulleted functions’ that could not exist without a complex control structure (I’ll write about this sometimes)
• Sequential ordering – this allows programmers to write APIs in such a way that using them requires invoking several functions in a predefined order.
• No matter how convoluted imperative programming can get, actions within a program ultimately aim at modifying runtime or persistent state.

Could modeling and programming using state transitions help increase the clarity and readability of code? This is the question I tried to answer. I’m now looking at typical function types, and what a state oriented perspective tells us about them:

Constructors

Constructors are used to setup the original state of an object. Ideally, the original state of an object can be easily specified using a hierarchy of elements – however, using imperative languages, we often need replacing this by lists of statements like:

ChildType x=new ChildType();
parentObject.addSomething(x);


Actions

An action is a function that modifies the runtime or persistent state of a system. In object oriented programming, an action executes from a locale and modifies state that is reasonably easy to reach from such locale. Often, the crux of any action is to prepare and execute a statement that will add, remove, set or clear a property related to the locale.
Invoking an action allows us to export state to a remote locale.

Queries

A query is a function which, ideally, modifies no state and is merely used to collect information from a given locale. Invoking a query allows us to import state from a remote locale.

Can I use this to improve code readability and simplicity?

Alas, how oft have I started writing a function with clear, straightforward intentions and eventually produced monsters that only the sleep of reason could emulate?

• Functions that dilute their original purpose in scores of preparation statements.
• Functions that modify program state in too many ways, with no clear view of where (within the function body) the states are affected.
• ‘Hidden’ actions modifying the state of my program while advertising query semantics.

As a rule of the thumb, if I can’t concurrently visualise the name of a function and the statement that realises its purpose, I feel something is wrong. Proposed remedies:

• After writing a function, immediately reconsider its implementation and sprout methods for complex preparation code. It is usually handy to add preparation code wherever needed while writing code, however this eventually makes implementations impossible to read (I wouldn’t sprout methods until after writing the code, because preparation code often needs researching, which requires a different kind of concentration).
• Avoid functions that concurrently return and modify state – with some exceptions: factory methods are usually fine; returning metadata (succes/failure flags) is sometimes okay (granted many of us think exception handling’s just better).

Even small functions can become fairly confusing because the preparation steps required to realise a state transition typically precede the statement realising the transition. The typical remedy is to bundle preparation code into separate methods. This allows shifting the emphasis back to the target statement while leaving granular details ‘for further reading’.

Pushing state orientation into language design

Recently, I’ve been trying to design a language to better support state orientation. Read on.

Drafting a Declarative Language

In this post, I draft a declarative language using a simple application as an example. Using an example helps me think about usability while drafting an artefact.

The target language is meant to provide enough power of expression to put together applications quickly using existing component libraries. Several ideas contribute to the design of this draft.

• Allow functions – functions are useful to ensure that the language is powerful enough.
• Avoid explicit control flow – control flow can easily make code hard to read.
• State orientation – behaviour is modeled as discrete state transitions.
• Separation between parsers and execution models – this may be essential to allow efficient integration of existing libraries and frameworks (I will discuss this somewhere else).

I use XML as a starting point, but I assume that the result may be translated into source for a language such as Java, C++ or Python. I dropped angled or curly brackets because I want a concise notation, so at first glance the resulting source looks like Python code.

Sample application

The sample application is a text editor. In spirit, this is a very cut down version of a couple of IDEs I’ve written before; an important requirement is that our text editor needs to be extensible.

Source code

The application uses the following files:

control
application.s

model
model.s
data_manager.s
TextDataService.s

view

view.s
view_manager.s
TextViewService.s

deployment
setup.s

Analysing the sample application

control -application.s

The control layer is implemented as a list of commands. In this source file, I establish a few conventions:

• The source file determines a runtime instance (not a class) [1]. That it is an instance is given by starting with a lower case letter [2]. This means that the [application] object is meant to be instantiated immediately when the application starts – in the same way that an html tag specifies an instance of the matching html entity.
• Since the existence of the file implies a container, we need not re-state such container within the file; as a result all commands are top level.
• Imports are denoted by & [3]. This is wholly equivalent to an import statement in Java, but I do not want to reserve words.
• Actions are functions that cannot return a value; actions are denoted by > [4]
• Annotations are denoted by @ and precede the annotated element [5]

I have implemented only one command.

>open
  view_manager.display(content,view.desktop)
  document: data_manager.forPath(path)
  path: openFile()


Notes about the above:

• Statements are listed in reverse order. This will seem counter-intuitive, but allows concentrating on the goal action first [6].
• The : colon notation is equivalent to  =  in Java [7].

I am not totally satisfied with the above – I would like to emphasize the fact that open() aims at adding a document and a view for this document. This would be simple (and also more declarative). I’ll come back to this later.

model – model.s

The model defines only the *forPath query required by application.s:

*forPath(path)
  data[path]
  #data[path]-: data_manager.forPath(path)


Additional notations are introduced here:

• The star symbol (*) denotes a query [8]. This allows a function to return a value.
• Query functions are evaluated in return scope [9]. Return scope is unboxed upon returning (here, data[path] is returned)
• Like actions, queries are evaluated bottom up.
• # defines an exception to the declarative query structure[10]. This means that the declaration prefixed by # is evaluated against the object scope, not the return scope. If we didn’t prefix using #, my guess is that an interpreter should define data and data[path] in return scope. But what we really want is define data[path] as data_manager.forPath(path).
• The notation -: indicates weak assignment [11]. Weak assignment implies that the right hand is evaluated and assigned only if the left hand is null or undefined.

data_manager.s manages data services:

*forPath(path,data)
  -services.*.load(path)
  -services.*.forPath(path,data.*)


This forPath query introduces two new notations:

• The dash symbol (-) , denotes weak assignment to return scope. This is not completely new and is meant to be consistent with the -: notation
• Used within a declarative statement, the star symbol (*) refers to any element [12]. In this case, services.*.load(path) indicates that load(path) is evaluated against
  all elements in services.

TextDataService.s is the only data service that I have implemented. This introduces no new notations except maybe the fact that *forPath(path,data) returns null by default.

view – view.s

View is the most simple object. This specifies a component hierarchy along with a shortcut to the desktop component. Note that most components are anonymous.

view_manager.s view manager redirects the display action to all available view services.
TextViewService.s implements the display(document,desktop) method required by view. The + sign indicates adding an anonymous element [13].

deployment – setup.s

This links view and data services for text using injection [14].