miniNOP

Reference code for miniNOP, a Minimum required interface for implementing the notification-oriented programming paradigm (NOP[1]).

In the NOP paradigm, in a simplified way, there are several FactBaseElements and several Rules. Rules have premises that check if FactBaseElements Attributes satisfy a condition. If the condition is satisfied, the action is executed, calling a function and being able to change the Attributes of the FactBaseElements again (and finally being able to activate other Rules); that is, the Rules has the function of notifying changes in the states of the FactBaseElements. The simplification of programming paradigms by defining a minimal interface to allow implementations in several languages is a promising attr. An example is miniKanren, which defines a minimal interface for logic programming, which allowed more than 170 implementations in the most diverse languages. In miniKanren, the reference code for implementation in the authors book takes up only 2 pages.

With that in mind, this implementation was developed, with only 253 lines of code, implemented in TypeScript, exploring the current limits of object orientation and imperative programming. The implementation has no dependencies on other libraries and can be used in any TypeScript/JavaScript runtime or modern browsers. Also, this implementation IS REACTIVE IN DEPTH.

Particularities of this implementation

In NOP we originally have the following entities: FactBaseElements, Attributes, Premises, Conditions, Rules, Actions, Instigations and Methods. In this implementation, we do not have entities to represent Attributes. Instigations and Methods, as they have been removed for convenience. So, we only have FactBaseElements, Premises, Conditions, Rules, and Actions. Actions directly represent a function reference. All system observable agents extend the FactBaseElement class and use the superclass method to access and set the observable values. The FactBaseElement class saves all these values in an internal observable map and the Premises of a Condition have as one of its parameters an instance of subtype (or type, FactBaseElement is also instantiable) FactBaseElement.

When implementing NOP in the von Neumann architecture with imperative programming we have the terrible complexity of O(n^3) in the worst case -> O(FactBaseSize(O(n)) * nPremises(O(n)) * nRules(O(n))). This implementation also don't use "infinite loops" and has a global FBE+Attribute x Premises MAP that associates an instance of FactBaseElement and a respective Attribute name to the Premises that use it. When an Attribute is modified, at the end of the modification it notifies the respectives Rules according to the FBE+Attribute x Premises MAP, in trigger style, no need to loop through the fact base (FactBaseElemens Attributes) to check for changes. With these optimizations we reduced the worst case upper bound to O(n^2) -> O(FactBaseSize(O(1)) * nPremises(O(n)) * nRules(O(n))). When an Attribute is modified, only the Rules that have Conditions with Premises that use the respective FactBaseElement and modified Attribute are re-evaluated. This doesn't change the average case upper bound, but it helps a lot in running the program. In the average case, the complexity is O(n) -> (numPremises + numRules). This implementation also considers the dependency of Rules: A Rule B can depend on a Rule A, and the Rule B is only evaluated automatic if the Rule A is satisfied. This dependency is also implemented in the trigger style. The computational architecture of the implementation can result in a "freeze" of the program if infinite changes of FactBaseElements states start, given the respectives Actions. To minimize this problem and at the same time implement the priority idea of Actions and Rules, when creating a Rule it is possible to insert an optional delay for its Action. Note that there is no need for a "Dispatcher" to queue notifications, as such notifications are implemented using ASYNC functions with delay. Depth reactivity allows modifications to an FactBaseElemens object's sub-attributes to represent changes in the FactBaseElemens object's state, triggering the respective Rules associated with it. For example:

//initial values
fbe.set(
  {
    a: {
      b: {
        c: "foo",
      },
      d: true,
    },
  },
);
/*
Rules that use "a", "a.b" or "a.b.c" will be re-evaluated.
Rules that use only "a.d" are not re-evaluated.
*/
fbe.set(
  {
    a: {
      b: {
        c: "bar",
      },
    },
  },
);

Conditions are implemented in a tree structure, easy for humans to understand. For each Condition, you must choose only one of the keys: "not", "and", "or", "xor" or "premise". Note that the "." is reserved in this implementation for path notation. This implementation does not handle circular references yet!. See examples of Conditions:

/*
PREMISE:
premise: {
  fbe => FactBaseElement instance.
  attr => path notation, ex: "target.person.age".
  is => "==", ">", "<", etc.
  value => //reactive FBEvalue or non-reactive constant.
},
CONDITIONS:
//with one premsie
{
  premise: premise1
}
//with OR, AND, XOR
{
  or | and | xor: [
    array of sub conditions
  ]
}
//with negation
{
  not: condition
}
*/
//EXAMPLE:
const c: Condition = {
  and: [
    {
      premise: <Premise> { //Types Premise and FBEvalue can be inferred, but we make it explicit to explain
        fbe: shooter1,
        attr: "gun.bullets ",
        is: ">",
        value: <FBEvalue> { fbe: shooter2, attr: "gun.bullets" }, //reactive FBEvalue
      },
    },
    {
      or: [
        {
          not: {
            premise: {
              fbe: shooter1,
              attr: "target",
              is: "==",
              value: true, //Non-reactive constant
            },
          },
        },
        {
          premise: {
            fbe: shooter1,
            attr: "gun.pull_trigger",
            is: "==",
            value: true,
          },
        },
      ],
    },
  ],
};

There is also an extension interface for named functions. See how to use:

Rule.registerExtensions([deepEqual]); //deepEqual = function with name "deepEqual", ex: function deepEqual(a: any, b: any): boolean { ...
//In conditions:
const c: Condition = {
  premise: {
    fbe: shooter1,
    attr: "character", //function name here
    is: "deepEqual",
    value: { name: "joe", age: 25 }, //Non-reactive constant, but it could also be an FBEvalue
  },
};

In the library package the extension functions "deepEqual", which checks in depth if two objects are the same, i.e. compares their parameters, subparameters and etc.

The code is very dense, although every detail has been thought of in order to favor readability and avoid replication. With TypeScript, we have a new way of defining types and programming in an object-oriented style compared to classic object-oriented languages such as Java and C++, which drastically reduces the amount of code. See the following code snippet:

export interface FBEvalue {
  fbe: FactBaseElement;
  attr: string;
}
export interface Premise extends FBEvalue {
  is: string;
  value: any | FBEvalue;
}
// ...
interface ConditionWithXor {
  xor: [Condition, Condition, ...Condition[]]; //min 2 conditions
  premise?: undefined;
  or?: undefined;
  and?: undefined;
  not?: undefined;
}
export type Condition =
  | ConditionWithNot
  | ConditionWithPremise
  | ConditionWithAnd
  | ConditionWithOr
  | ConditionWithXor;
export class Rule {
  static #FBEattrMap: {
    [key: string]: Map<FactBaseElement, Set<Rule>>;
  } = {};
  static #extensions: {
    [key: string]: Function;
  } = {};
  #transpiledFBEs: FactBaseElement[] = [];
  #transpiledCondition: () => boolean;

Sample application

This program contains an example of an application called "Target shooting".

class Shooter extends FactBaseElement {
  shoot() {
    super.set(
      {
        gun: {
          bullets: 5,
          pull_trigger: true,
        },
        target: true,
      },
    );
  }
}

const shooter1 = new Shooter();

const rule1 = new Rule(
  {
    premise: {
      fbe: shooter1,
      attr: "gun.bullets",
      is: ">",
      value: 0,
    },
  },
  () => console.log("loaded gun!!!"),
);

shooter1.shoot();

Instructions to run this project

Basically you just need to clone the project and install the Deno runtime.

# clone project
git clone https://github.com/hviana/miniNOP.git
# enter the project directory
cd miniNOP
# install Deno (Mac, Linux)
curl -fsSL https://deno.land/install.sh | sh
# install Deno (Windows)
iwr https://deno.land/install.ps1 -useb | iex
# run project example:
deno run example.ts
# bundle miniNOP lib to any runtime or web browsers:
deno bundle mod.ts nop.js

References

[1] J. M. Simão, C. A. Tacla, P. C. Stadzisz and R. F. Banaszewski, "Notification Oriented Paradigm (NOP) and Imperative Paradigm: A Comparative Study," Journal of Software Engineering and Applications, Vol. 5 No. 6, 2012, pp. 402-416. doi: https://www.doi.org/10.4236/jsea.2012.56047