Saturday, July 27, 2019

Embedded Languages: The Space Between Language and API

We're all familiar with general-purpose programming language for capturing general algorithms, but there are also a sizeable group of domain-specific languages that exist to efficiently capture reasoning in a specific domain -- whether that's hardware design (Verilog, VHDL), database manipulations (SQL), or models at a high level of abstraction (UML/xtUML). These languages exist because the overhead is enormous for a domain expert to capture a problem in their given domain using a general-purpose programming language and APIs.

One of my favorite examples showing the motivation for domains-specific languages is spreadsheets. A spreadsheet is a language based around a namespace (table) where elements (cells) in the namespace are addressable by their coordinates, and whose values are represented by equations that may include references to other elements in the namespace. Just think how easy it is to setup a simple spreadsheet to do some what-if analysis, and how difficult it would be if you had to write a program to perform those calculations instead!

Simplistic though it may be, the spreadsheet perfectly captures the motivation behind domain-specific languages: focus on capturing the what of a given domain -- the key attributes, key relationships, and key operations -- and not on the how of the mechanics of how these elements would be represented in a general-purpose programming language. In short, a domain-specific language provides a user interface to complex algorithms phrased in familiar terms -- at least to someone knowledgeable in a that specific domain.

Taking the step of capturing domain knowledge in a new domain-specific language is a big step, though. There are a variety of reasons to defer taking that step or, perhaps, to not take that step at all.  Sometimes an entire language isn't required to implement the desired user interface. Sometimes it's desirable to have some benefits of a general-purpose language without the overhead of designing an entirely new all-in-one domain-specific and general-purpose language. The embedded domain-specific language is one approach that has been used to bring some benefits of a domain-specific language into an existing general-purpose programming language. The general approach is to use existing general-purpose language constructs, such as pre-processor macros and operator overloading, to build constructs with a domain-specific language feel within an existing language.

Within the set of embedded domain-specific languages that I'm aware of, I'm actually aware of three key styles of embedded a domain-specific language inside an existing general-purpose programming language.

Decorations and Annotations
One of the simplest domain-specific language integration techniques that I'm aware of is the decorator/annotation pattern. This style of domain-specific language is used to statically register classes or functions with a library framework.
class slave_address_map_info extends uvm_object;
  protected int min_addr;
  protected int max_addr;
  function new(string name = "slave_address_map_info");;
    `uvm_field_int(min_addr, UVM_DEFAULT)
    `uvm_field_int(max_addr, UVM_DEFAULT)

  // ...

While there are many examples of a decorator/annotation eDSLs, the example that came to mind first for me was the Universal Verification Methodology (UVM). UVM is a class library for functional verification built on top of the SystemVerilog domain-specific language. Two common operations that users of the UVM need to perform is registration of key user-defined types with the class library, and writing functions to clone, compare, and print class instances. Performing these operations in plain old code is time-consuming and error-prone. UVM provides a set of macros that allow the user to declare the existence of their user-defined class type and the fields within it (shown above highlighted in blue). 
The macros (SystemVerilog's key feature supporting embedded domain-specific languages) above cause the class type to be registered with the UVM class library, and implement functions for comparing, displaying, and cloning an object of this type. All from a high-level specification.

Enmeshed eDSL
Our next level of eDSL integration starts to look a bit more like a language. An Enmeshed eDSL provides the user statements that look a bit like a programming language, but are really driving algorithms behind the scenes. I call this style of integration Enmeshed because the user's general-purpose programming language code interacts closely with the algorithms driven by the eDSL as program runs.
class item : public rand_obj {
item(rand_obj* parent = 0) : rand_obj(parent), src_addr(this), dest_addr(this) {
src_addr.addRange(0, 9);
src_addr.addRange(90, 99);
constraint(dest_addr() % 4 == 0);
constraint(dest_addr() <= reference(src_addr) + 3); 

randv<uint> src_addr;
randv<uint> dest_addr;
Our example of an Enmeshed eDSL comes courtesy of CRAVE, a constrained-random data generation package for the C++-based SystemC library. As you can see, the highlighted sections above look a bit more like a language. In this case, these are constraint expressions that control a constraint solver such that the values of src_addr and dst_addr obey the relationships established by the expressions.
When the user's program runs, it creates instances of classes like the one shown above, calls an API to create new random values for the random fields, and uses the values from those fields directly. In short, I consider the eDSL enmeshed with the host language because execution of the host language is interleaved with (effective) execution of the eDSL. The host language takes a primary role, and calls the eDSL code to provide specific services to the primary application.

Encapsulated eDSL
Our final level of eDSL integration is an embedded DSL that defines a new domain within the host language. There are several hardware-description languages embedded in general-purpose programming languages that fit this definition.

import chisel3._

class GCD extends Module {
  val io = IO(new Bundle {
    val a  = Input(UInt(32.W))
    val b  = Input(UInt(32.W))
    val e  = Input(Bool())
    val z  = Output(UInt(32.W))
    val v  = Output(Bool())
  val x = Reg(UInt(32.W))
  val y = Reg(UInt(32.W))
  when (x > y)   { x := x -% y }
  .otherwise     { y := y -% x }
  when (io.e) { x := io.a; y := io.b }
  io.z := x
  io.v := y === 0.U

I've selected CHISEL (Constructing Hardware in a Scala-Embedded Language) as the example. What makes an encapsulated eDSL different is that the description made using the eDSL is monolithic and executed to create a single model -- in this case, Verilog. The GCD design show above might be used within a larger CHISEL-based design, but would never be used within a user's program to provide a useful service to the program. In a sense, an encapsulated eDSL description takes on a primary role within the host application. 

Embedding a DSL in Python
As we've seen, an embedded domain-specific language can provide a domain-specific interface to complex algorithms inside the confines of an existing general-purpose programming language. We've looked at several styles in which an embedded domain-specific language can be integrated into its host language -- all with different tradeoffs in terms of benefits and usability.
I've personally worked with embedded domain-specific languages in nearly every programming language I've used -- from C/C++ to TCL to Java. Most recently, though, I've been learning Python and (naturally) exploring the capabilities that Python offers for supporting an eDSL. Over the next few posts I'll look at Python's features that enable eDSL integration using a small eDSL I've been working on as an example.
In the meantime, what has your experience been with embedded domain-specific languages? Helpful or frustrating? Any notable examples -- either good or bad?

The views and opinions expressed above are solely those of the author and do not represent those of my employer or any other party.

Saturday, July 13, 2019

The Toolmaker's Dilemma: Visionaries Have Always Created Their Own Tools

I recently saw a quote (on Twitter, in a photo no less) to roughly the same effect as the title above: that innovators and visionaries have always created their own tools. I'd attribute the quote if I could, but the dynamic nature of Twitter has ensured that my chances of locating the original post are slim to none. Nonetheless, I've been thinking quite a bit about the concept over the last few weeks. First, whether the claim is true. Secondly, if true, whether this is a good, bad, or neutral thing. And thirdly, what, if anything, could or should be done to change the situation.

Who Are the Visionaries?

One of my favorite Geoffrey Moore books is Crossing the Chasm, which I've read this multiple times over the course of my career. Despite some of the example in the book being a bit dated, much of the advice is still relevant and I feel that I come away with new insights every time I read the book.

Moore identifies Visionaries as the Early Adopters in his book.
Visionaries are that rare breed of people who have the insight to match an emerging technology to a strategic opportunity, the temperament to translate that insight into a high-visibility, high-risk project, and the charisma to get the rest of their organization to buy into that project. 
Visionaries drive the high-tech industry because they see the potential for an "order-of-magnitude" return on investment and willingly take high risks to pursue that goal. 
Moore sees Visionaries as seeking monetary return on investment, and I've encountered many of these. However, I've also encountered Visionaries that are looking for different types of return on investment -- for example, fundamentally altering the way an industry approaches functional verification methodology.

The Opportunities and Challenges of Visionaries

Engaging with Visionaries, as with all of the personalities across the technology adoption curve, has its opportunities and challenges. Visionaries have a clear and ambition vision of the future, and are highly motivated to realize that vision. On the flip side, Visionaries make for demanding customers. Quoting Moore:
As a buying group, Visionaries are easy to sell to but very hard to please. This is because they are buying a dream -- which, to some degree will always be a dream.
Visionaries are also, by definition, out of step with the majority and early majority portions of the market where you hope to get your tool adopted, and often 5-10 years ahead. This can be a good thing if you buy into their vision of the future. However, it's often unclear whether their ideas are crazy good or just crazy.

Moore advises an approach of partnership with Visionaries. This can be a good approach for truly early stage technologies, provided the Visionary is backed by an organization with deep pockets (either financial or people resources), and provided that you buy into their vision of the future. When these criteria are not met, it's very likely a "business decision" will be made to not engage with the Visionary since engagement won't help the product get to its intended destination.

Why do Visionaries Build their Own Tools?

The decision to not engage with a Visionary is typically done for good and rational reasons. After all, the market is optimized to target the majority -- and this is true both for commercial and non-commercial endeavors. However, the story often doesn't end here. Remember, Visionaries are highly-motivated people and driven to realize their view of the future.

A not-infrequent result is that Visionaries collect pieces of available technology and proceed to implement a version of the tool of their dreams. So, the short answer is that Visionaries build their own tools because they feel they haven't any viable alternatives.

What's Wrong with this Picture?

So, is this really a problem, or just the way technology needs to evolve? After all, the best way to determine whether an idea is crazy-good or just crazy is to wait and see if it gains traction or withers away. Just like biological evolution, this makes sense in large ecosystems. Losing a few crazy-good ideas along with the plain crazy ideas in a large ecosystem is just a cost of doing business.

However, many of us find ourselves, by choice or circumstance, in much smaller niche ecosystems. Here, fostering innovation is key to growing the ecosystem. Losing a few crazy-good ideas makes a big difference here. And, the fact that Visionaries are off building out their visions on the fringes of the ecosystem has the effect of further subdividing an already-small ecosystem.

A Venture Capital Approach to Visionaries

If you find yourself in a niche ecosystem -- whether commercial or open source -- I would encourage you to take a venture capital approach to supporting the work of Visionaries. What do I mean by this? Make some bets to enable the work of Visionaries in the tool you provide to the market, and provide ways for Visionaries to interact with your tool's community. Much like the investments venture capital makes, the assumption is that most of these bets won't pay off, but that a few will pay off in a big way.

One big thing that has changed since Geoffrey Moore wrote Crossing the Chasm in 1991 is just how easy it is for communities (even niche ones) to connect and interact. This provides fundamental new opportunities when it comes to propagating new technology to technology ecosystems, and merits a rethink in the way we approach the relationship between new technology and visionaries.

In some sense, the suggestion above changes relatively little about the way we build and promote tools. We often accidentally build in capabilities that visionaries can use. However, I believe we can get even better results by deliberately and intentionally creating these visionary-friendly mechanisms. Plan and develop extension mechanisms that don't impact usability for mainstream users, but allow visionaries to implement their visions in the context of your tool instead of needing to create a completely-separate tool. Keep visionaries close to your community of existing users so they have a ready audience to help accelerate the process of identifying crazy-good ideas and weeding out plain-crazy ideas. Be on the lookout for those truly crazy-good ideas that resonate with your community and have potential to be the next big thing.

The views and opinions expressed above are solely those of the author and do not represent those of my employer or any other party.