Ensō Grammars

I have not had much time to write about Ensō recently, because I’ve been too busy building Ensō. Bruno Oliveira visited last week and we worked out some interesting new ideas for transforming circular structures. There are cases where the input is circular, the output is circular, and also when the operation itself is circular (needing a fixpoint). Bruno is working in a pure functional setting, but we are doing analogous things in the Ruby implementation of Ensō. Tijs van der Storm is still here until the beginning of July. Alex Loh, a PhD student in my group, has also joined the team. Things are going well, although my implementation of the diagram editor is going a little slower than I had hoped. But no problems yet.

Last time I talked about schemas and said I would talk about parsing this time. It turns out that parsing is still an interesting topic, even though its been worked on extensively. Here is the simple schema, for points, which I mentioned in the last post:

class Point
x: int
y: int

A grammar to recognize points in standard notation is easy to define:

start P
P ::= "(" int "," int ")"

As is typical, an Ensō grammar is a list of rules with a start symbol. The right hand side of a rule contains literal strings “(“, “,” and “)” and generic tokens, e.g. int. The Ensō tokenizer has predefined syntax for strings, identifiers, and numbers, but allows the grammar to define arbitrary operator/punctuation tokens. This grammar can recognize strings that have the form (-12, 42). To be useful a parser must create objects, not just recognize syntax. The following grammar creates points:

start P
P ::= [Point] "(" x:int "," y:int ")"

The expression [Point] means that the rule creates a point. The notation x:int means that an integer is recognized, then assigned to the x field of the current object being created. The end result is that the rule creates a point and assigns its x and y fields.

This example illustrates that an Ensō grammar can create objects directly, rather than creating abstract syntax tree (AST) as in most grammar formalisms. In other words, the result of parsing is a point, not syntax that later creates points. Ensō grammars only create syntax trees when they are parsing a schema that represents syntax of a language. Points aren’t syntax, so there is no need to create syntax trees when parsing them.

The second important fact about Ensō grammars is that they are bi-directional. The grammar can also be used to render a point into a text string. Under this interpretation of the grammar, the expression [Point] is a condition or predicate that matches objects of type Point. The expression x:int means to access the x field of the current object and render it as an integer. The result is a string of the form (5, -3).

The bidirectional nature of grammars is a result of the weaving of two different languages in the grammar notation: the syntactic structure, represented by literals “(“, “,”, “)” and int tokens, and the instantiation structure represented by class names [Point] and fields x: and y:. A parser matches the syntactic structure and creates the object instantiation structure. A renderer matches the object instantiation structure and generates the syntactic structure.

In my previous post I presented several schemas and introduced a notation for describing schemas. We can now formally specify this notation. For convenience, here is a version of the final schema that we introduced, the Schema Schema.

class Schema
  types: Type*
class Type
  name: string
class Primitive < Type
class Class < Type
  super: Class?
  fields: Field*
class Field
  name: string
  type: Type
  many: bool
  optional: bool
primitive string
primitive bool

The Schema Grammar defines the language in which this schema is written. It looks like this:

start Schema
Schema ::= [Schema] types:Type*
Type ::= Primitive | Class
Primitive ::= [Primitive] "primitive" name:str
Class ::= [Class] "class" name:str Super? fields:Field*
Super ::= "<" super:^Class
Field ::= [Field] name:str ":" ^Type (optional:"?" | many:"*")

The rules correspond fairly closely to the structure of the schema itself, so it is convenient to use the same names where appropriate. It can also be confusing. Just keep in mind that the names on the left of ::= are the names of nonterminals, and they could be renamed to be any names at all. There is a special case for boolean fields: the notation optional:”?” sets the optional field to true if the symbol “?” is present. There are two places where schema class names show up in the grammar. One is an object instance expressions, e.g. [Field]. The other is an object reference expressions, e.g. ^Type, described below. Here is an equivalent grammar, where the nonterminals have all be renamed.

start S
S ::= [Schema] types:T*
T ::= P | C
P ::= [Primitive] "primitive" name:str
C ::= [Class] "class" name:str U? fields:F*
U ::= "<" super:^Class
F ::= [Field] name:str ":" ^Type (optional:"?" | many:"*")

Again, parsing a text file with this grammar does not create abstract syntax, it creates an actual schema.

The reference syntax ^Class allows the parser to automatically create circular references in the resulting structure. The expression ^Class means that a name for a class is parsed, then during object construction the parser replaces the name with a pointer to the Class with that name. During rendering, the opposite happens: the Class is rendered by printing its name. This brings up the question of how the grammar knows what field to use as the name of a class. It doesn’t just use the name field. Instead the real Schema Schema has an extra attribute on fields that specifies which field acts as the key for identifying objects. In the class Class, the field named name is marked as the key field. (I’m sorry for that last sentence. It is typical Ensō-speak, brought on by using the words “name” and “class” as categories and instances in the same sentence).

Notice that not every rule has a constructor. For example, the Super rule (aka U) just reads in part of a class object, so it does not create any objects on its own. Of course, the Super rule could also be inlined into the Class rule:

Class ::= [Class] "class" name:str ("<" super:^Class)? fields:Field*

In fact, everything could be inlined in this grammar, because it is not recursive. But then it would be a little more difficult to read:

[Schema] types:
    ( [Primitive] "primitive" name:str
    | [Class] "class" name:str ("<" super:^Class)? fields:
        ( [Field] name:str ":" ^Type (optional:"?" | many:"*" )*
    )*

This grammar is just a regular expression. Ensō grammars include regular expressions as a special case.

The parser is a grammar interpreter, not a grammar compiler. The underlying technology is called Generalized LL (GLL) parsing. It can parse arbitrary context-free grammars with left recursion. The overall parse must be unambiguous, but there is no need for the syntax to be locally ambiguous based on fixed lookahead. I hope that Tijs will write a blog post explaining how the parser actually works, at some point. The basic algorithm is not very interesting, but the way it works with the rest of Ensō has some interesting points.

After my last post, some people got the impression that Ensō is a data description language. With this post, I’ve extended that impression slightly to be data description and formatting. We are creating lots of different modeling languages in Ensō, so one way to understand Ensō is that it is an environment for creating and integrating multiple domain-specific languages. Ensō is a full programming model, so there has to be some code somewhere. Unlike most approaches to model-driven development, we don’t generate any code in Ensō. Instead we directly interpret the models to create useful behaviors. This is more direct, because its the behavior we want, not the intermediate code.

For the foundational models, like schemas and grammars, we have hard-coded Ruby interpreters. The Ruby code looks pretty good, but its not exactly ordinary OO Ruby code, because the data it manipulates is Ensō data. As we move into interpreters for high-level models, we are finding a need for higher level programming patterns that manipulate circular structures. This code may be functional in nature, or more imperative. Writing functional style is nice, but the circularity of Ensō data means that ordinary functional programs, based on induction, don’t work correctly. We have developed some nice techniques for transformation of cyclic structures. For imperative code we are exploring ideas of Jonathan Edwards to decouple imperative operations and sequencing of operations. Some of these ideas are still in development, but they are coming along nicely. Next time I’ll write about the Grammar Grammar, which defines the syntax of grammars.

Ensō Data

The foundation of the Ensō programming model is the representation and manipulation of data. We are borrowing ideas from database and information modeling, and turning that into a data structuring mechanism that makes sense in a programming language. When you think of data structures as mini databases some interesting things can happen. Most importantly, it encourages thinking of data holistically rather than as individual objects or individual data types. It also enables us to rethink the idea of “types” in programming languages.

Programming languages can be divided into two camps: those with static type checking and those with dynamic type checking. The static ones allow programmers to describe the structure of their data and then create and manipulate values that have the specified structure. Since these type systems are checked statically, they traditionally only describe the structure of values, not semantic constraints. It is also possible to define abstract data types, which wrap a primitive data structure with operations that enforce semantic constraints. More recently there has been extensive work on adding more semantic constraints into static types, although there is significant tension due to the need for static verification of the types. Existing dynamically typed languages have a built-in set of predefined data structures, which the programmer uses to create larger structures. In many cases these higher-level structures are never described explicitly. Dynamically-typed object-oriented languages allow programmers to wrap dynamic data with methods to enforce semantic constraints. Objects implement the constraints locally and operationally. There typically is no declarative global view of the semantic constraints that the programmer intends on the data.

Ensō adopt the descriptive and declarative view typical of static type systems, but uses dynamic checking so that arbitrary behavioral constraints can be included in the descriptions. Because we are exploring new territory, we avoid using the word “type” in talking about Ensō data. We use the term “schema” instead, borrowed from the database literature.

This leads to the first principle of Ensō, which is that all data is described by schemas. A schema specifies the properties and constraints on a kind of data. For example, if we want to describe 2D points, we might say “A point has an x and a y component, which are integers.” This is corresponds to the following schema:

class Point
  x: int
  y: int

This defines a class named Point with two fields, named x and y. We use the generic term field to describe a named component of a structure. In the next post I’ll talk about how to write a grammar for points, but for now we can assume that points can be written in the normal way, e.g. (3, 6). Also, given a point P, we can access the fields in the normal way, as P.x and P.y. We will also talk about constraints later. For now I want to talk about some more complex structures and then circularity of descriptions. Continuing with larger structures, we can define rectangles and polygons:

class Rectangle
  top_left: Point
  bottom_right: Point
class Polygon
  points: Point*

The * means that a polygon has a list of (zero or more) points. This example also shows that the type of a field can either by a primitive type, int in the case of x and y, or a complex type Point the case of top_left and points. Note that some of the typical data structuring ideas, like List<Point>, which are usually explicit in a programming language, are implicit in Ensō. We will also talk about how to create and manipulate rectangles and polygons later. There are many things to talk about, and I’m sorry I can’t do it all at once. For now I have a specific agenda, as you will see in a minute.

The schema above is called the Point Schema or Geometry Schema. This is because it is a schema and it is about points, or geometry. We can create many kinds of schemas in Ensō, to represent many kinds of data. For example, a Genealogy Schema could describe the structure of genealogical data, a Mail Schema could describe the emails in an email program, a Diagram Schema could describe the structure of visual diagrams, and a File System Schema could describe the structure of files and directories in a file system. I will talk about all these examples, and more, some other time. Buts its not rocket science. If you know Entity Relationship (ER) modeling, or Class Diagrams in UML, then this process of creating schemas will be familiar. What might be a little strange is writing these schemas down and calling them a “programming language”. I mean, I haven’t even told you how to write “Hello World!” yet. But trust me, these schemas are programs, in the sense that they can be used to create/manipulate data. (Oh, and I never will tell you how to write Hello World… it’s not interesting). For now I want to focus on something that might be more interesting, which is circular descriptions.

These descriptions are also data. From this and principle #1, it immediately follows that schemas are described by a schema. This means we need to write down a schema the describes the structures we’ve be writing above. In programming terms, what we need is a type of types. This meta-schema needs to say something like “a class has a name and a list of fields, which specify their name and type”.

class Class
  name: string
  fields: Field*
class Field
  name: string
  type: ???

This is a good start at a schema that describes schemas. We had a little problem writing it down, because the type of a field can either be a class or a primitive type (Point or int in the examples above). The structure we need is familiar: a generic category called Type that has two specific realizations Primitive and Class. This is a class hierarchy. One thing that Primitive and Class have in common is that they both have names, so we can put that field into the base class. Another problem with the schema is that it has two classes, which work together to describe classes. Thus it would be good to be able to organize collections of classes. Lets introduce this into our schema:

class Schema
  types: Type*
class Type
  name: string
class Primitive < Type
class Class < Type
  fields: Field*
class Field
  name: string
  type: Type

The notation < Type means that Primitive and Class are subclasses of Type. This is now a very nice description, and it is capable of describing the Geometry Schema given above. Using YAML notation, the explanation of the Point Schema in terms of the meta-schema would look something like this:

class Point
 x: int
 y: int
Schema:
- Class:
    name: "Point"
    fields:
    - Field:
        name: "x"
        type: *int
    - Field:
        name: "x"
        type: *int
- Primitive &int
   name: "int"

On the left is the point schema, and on the right is an encoding of the Point Schema where its schema structure is made explicit. In our use of YAML, the top level is the class name, and then the fields are listed below. The fields values can either be primitive data, or more complex fields. The label &int identifies the primitive type named “int” which is referred to via *int for the type of the x and y fields. (Technically the label should come first, but this is pseudo-YAML, not real YAML). The left is quite nice, but the explanation on the right is not a pretty thing to look at. But it is useful to understand the mapping between them. As another simple example, a point would look like this:

(3, 7)
Point
  x: 3
  y: 7

The above example shows that our proposed Schema Schema is able to describe the Point schema. Note how the complexity goes up rapidly as we move from points to descriptions of points to descriptions of descriptions of points.

If you think about the corollary above, that schemas are described by a schema, it should be clear that there is potential for infinite regress. If everything is described by a schema (principle #1), and schemas are described by schemas (corollary #1) then the only way to avoid regress is if some schemas describe themselves. This is what the Schema Schema must do. It is a schema that describes the structures of schemas, including itself. As it stands, there are two features that are used in the proposed Schema Schema that it is not able to explain: subtyping and collection fields. These are represented by the < and * symbols above. Its easy to explain collection fields, by simply adding a boolean flag to each field that specifies whether the field is single-valued or multi-valued. A super class can also be listed on a class definition:

  class Schema
    types: Type*
  class Type
    name: string
  class Primitive < Type
  class Class < Type
    super: Class
    fields: Field*
  class Field
    name: string
    type: Type
    single: bool
  primitive string
  primitive bool

Ooops! We have a problem: not every class has a superclass. Thus we need to allow the superclass field to be optional. If we do this, then we have to have an explanation for fields whose value is optional as well. We will use the symbol ? to indicate optional values, and then add an optional attribute to the description of fields:

  class Schema
    types: Type*
  class Type
    name: string
  class Primitive < Type
  class Class < Type
    super: Class?
    fields: Field*
  class Field
    name: string
    type: Type
    single: bool
    optional: bool
  primitive string
  primitive bool

For completeness, we also added descriptions for the primitive types used in the schema.

Now this is a schema that describes itself. It is a slightly simplified version of the Schema Schema in Ensō. The explanation of how the Schema Schema describes itself is ugly, but it is interesting to see how the structural description contains data that is analogous to the structure:

Schema:
  types:
  - Class:
      name: "Schema"
      fields:
        - Field:
             name: "types"
             type: *Type
             single: false
             optional: false
  - Class &Type
      name: "Type"
      fields:
        - Field:
            name: "name"
            type: *string
            single: true
            optional: false
  - Class
      name: "Primitive"
      super: *Type
  - Class &Class
      name: "Class"
      super: *Type
      fields:
        - Field:
            name: "super"
            type: *Class
            single: true
            optional: true
        - Field:
            name: "fields"
            type: *Field
            single: false
            optional: false
  - Class &Field
      name: "Field"
      fields:
        - Field:
            name: "name"
            type: *string
            single: true
            optional: false
        - Field:
            name: "type"
            type: *Type
            single: true
            optional: false
        - Field:
            name: "single"
            type: *bool
            single: true
            optional: false
  - Primitive &string
      name: "string"
  - Primitive &bool
      name: "bool"

Explanations are often more complex than the simple facts. The original scheme is highly circular, and this explanation makes the circularity explicit. In particular, the definition of the class Class is labeled &Class, and this is used in the type of the super field that is inside the class Class. Remember that Ensō means circle 🙂

This kind of meta-circular description is well known in the literature. It is used in Smalltalk and the the Meta Object Facility (MOF) of UML. It has also been studied in programming languages. Some languages have explored the idea of allowing types to have types, and the possibility of a type of types. There might be theoretical issues with having a type of types, but we are having too much fun programming with Ensō to worry about it. Also, in Ensō we merely say that the schema describes itself. We don’t think of schemas as “sets of values” so there is no issue of a set that contains itself.

The Schema Schema given above is not exactly the one we use in Ensō right now, but it is  close. I’ll talk about some other features over the next few weeks. We are implementing Ensō in Ruby, but last week I played with encoding the Schema Schema in Haskell. I’m not sure what we could do with it yet, but it is fun to look at.

Ensō Introduction

I know that this is just a teaser, but it is the introduction of the paper on Ensō that Tijs and I are writing. If you want to know more or see the code, let me know.

Ensō is a theoretically sound and practical reformulation of the concepts of model-driven software development. Ensō is based on first-class structural descriptions, invertable transformations, generic operations and interpretation.

Structures in Ensō are a specialized kind of graph, whose nodes are either primitive data or collections of observable properties, whose values are either nodes or collections of nodes. From a programming language viewpoint this may seem an odd choice for data representation. However, it is essentially the Entity-Relationship (ER) model, also known as Information Models, which is widely used in the design of relational databases and is also the basis for Class Diagrams in the Unified Modeling Language (UML), which describe the structure of networks of objects. The key point is that structures in Ensō are viewed holistically as graphs, not as individual values or traditional sums-and-products data structures.

A structural description, or schema, specifies some of the observable properties of structures. Schemas are used to check the consistency structures. Some properties can be checked while the structure is being created, but other can only be checked once the structure is complete. Ensō allows modification of structures, which is necessary to create cyclic graphs, but also allows valid structures to be sealed to prevent further changes.

Invertible transformations are used to map one structure into another kind of structure, such that mapping can be inverted to (partially) recover the original structure from the result. One common kind of transformation is called a grammar, which is an invertible transformation between structures and text. Text grammars are invertable because they can be used for parsing and also rendering. Other transformations include Diagram grammars, which map structures into diagrams, were edits on the diagram are reflected in the original structure. Grammars that describe the structure and behavior of user interfaces are used to generate very natural applications. Transformations are also used for querying, template processing, and serialization.

Operations can be guided by schemas or grammars, allowing highly generic operations to be defined for comparison, differencing, merging, projecting and otherwise manipulating cyclic structures. These operations are cyclic maps, which correspond to coinductive transformations. Since schemas and transformations are also structures, they can be merged and transformed using these same generic operations. Transformations on schemas can be applied to instances, to support upgrade and change management of data. The resulting system supports powerful modularity constructs, including feature modules, inheritance, and mixins.

Ensō is based on interpretation rather than code generation. While it is possible to define transformations that generate code in conventional languages, this is rarely (if ever) done in Ensō. Instead all structural descriptions and transformations are interpreted dynamically. Although the current incarnation of Ensō does not include it, we have previously demonstrated that partial evaluation can be applied to Ensō-style interpreters to automatically generate efficient code.

Get plugin http://www.fastemailsender.com