Introduction

Many people in software speak of top-down and bottom-up programming . These approaches are acceptable for building out systems depending on your use case. However, there is another lesser-known approach that I would like to discuss. Middle Out Programming, more recently termed Language Oriented Programming, is an exciting way of thinking about your problem.

In top-down programming, we start with a high-level algorithm or solution and then break that down into smaller and smaller fragments. Finally, implementing those fragments. In bottom-up programming, we begin with small pieces or utilities and stitch together a more complex system as our solution. Middle-out programming starts with creating a domain-specific language describing your domain space and then implementing your application/solution using your DSL. Finally, you can implement your DSL (Domain-Specific language). There is a paper that describes the background of middle-out programming here.

When first researching this topic, I needed help finding examples that were simple to understand. A friend recently told me that I should build Tic Tac Toe. To help us build out Tic Tac Toe, I will approach this problem middle out.

The Steps of Middle Out Programming

1. Create a DSL
2. Write a Solution to a Problem in DSL
• revise DSL as needed
3. Implement Evaluators

Creating a Domain-Specific Language

When researching language-oriented programming, the most significant pain point is motivating language design for your problems. I have taken the following from insights I have gained from the Programming Language community.

A language has two main features:

• Primitives.
  • A unit of work that makes sense in your context.
  • core structures
  • unbreakable pieces
• Operations
  • Actions you can take with primitives.
  • means of abstraction
  • mmeans of application

How do we determine what operations and primitives are for any given space? There are many answers to that question; the easiest is just being the domain expert yourself. However, we only have the luck of being the domain expert sometimes. In cases where we aren't lucky, we can use contextual inquiry and User Research to garner insights. I will cover those topics in a later post.

Programming your DSL

Once we have arrived at a good set of operations and primitives for our domain, we can start thinking about implementing our language. If you are using a language like Elm or Haskell, you could do this by defining a new datatype that looks something like this.

type Expr =  Primitive1 | Primitive2 | Op1 Expr  
 

We create data constructors for our primitives and operations. The key note here is that we have defined our type recursively. So, for example, op1 depends on a particular kind of Expr that can only be one of our primitives. This recursive structure makes for a composable design.

You would write macros to create your languages in a language like Lisp or Elixir.

Now you have your AST or macro's written. It's time to try and solve your problem using the language you created. Using those primitives and operations, can you devise a solution to your problem? If the answer is no, you need to modify your underlying language. You only want to add the least amount of required functionality when you do this. We can move on to the last step if the answer is yes.

Writing the Evaluators

Finally, we have this language of primitives and operations. We have a solution to our problem written in this language. How do we extract meaning from our DSL? We create a type of function called an evaluator. An evaluator takes an expression written in some language and derives meaning by coming to a value for the given term.

Let's say, for example, we have a language that describes adding numbers. The AST might look like the following :

type NumExpr = Add NumExpr NumExpr | Num  
 

That looks good enough. We know we can add numbers at this point with our language. Now we need to write some evaluators to derive meaning from our DSL. For example, we could say that we want to know the answer to Add 3 4, which would be 7, or we could say we wish to see the English sentence for this statement.

"The result of adding 3 and 4 is 7." 

In this case, imagine having two separate evaluators, one for a math context where we need the actual numbers back. Another where maybe we are dealing with logs of our computation and need to see strings. We gain flexibility because our business logic isn't in our lower implementations benefiting from the top-down style. And now we only build out utilities necessary for our task.

This post has gotten long. Therefore, I will begin with the Tic Tac Toe example in the next post.