flisp.py: a simple predicate evaluator

README.md

Blog 2018/8/4

<- previous | index | next ->

flisp.py: a simple predicate evaluator

At work we needed to come up with a way to evaluate boolean predicates in a dynamic, multi-platform manner (e.g. for client-side A/B test bucketing).

What we came up with was a simple Lisp-like language, where all expressions (in JSON format) evaluate to a boolean value (if an expression cannot be evaluated, it is assumed to be data).

We implemented flisp in Swift, JavaScript, TypeScript, PHP, and Python. This is the Python implementation, which served as the initial proof-of-concept.

For example, given an env of

{"user.isPremium": true, "user.sessionCount": 4}

the JSON expression

["and", ["env", "user.isPremium"], [">=", ["env", "user.sessionCount"], 4]]

would evaluate to true.

As a bit of syntactic sugar, symbols prefixed with a $ were pulled from the environment, so the above expression is equivalent to

["and", "$user.isPremium", [">=", "$user.sessionCount", 4]]

Operators:

env, and, or, not, in, =, !=, <, >, <=, >=

Types:

bool, string, int, float

env

It was intended that the values available from env would grow over time.

flisp5.py

#!/usr/bin/env python

import sys
import json

"""
flisp5:

ops: env, and, or, not, in, =, !=, <, >, <=, >=
types: bool, string, int, float
env: user.isPremium, user.isLoggedIn, user.sessionCount

all expressions must evaluate to a bool.

if an expression cannot be evaluated, it is assumed to be data.

strings prefixed with $ are substituted from the env.
"""

class FlispVM:

    env = {}

    def eval_str(self, string):
        result = self._eval(self._parse(string))
        if not isBool(result):
            raise ValueError('Expected final expression to evaluate to a bool, have %s' % result)
        return result

    def _eval(self, expr):
        # print "_eval", expr
        if isBool(expr):
            return expr
        elif isNumeric(expr):
            return expr
        elif isString(expr):
            if expr in self._ops.keys():
                return self._ops[expr]
            elif expr.startswith('$'):
                return self._env([expr.lstrip('$')])
            else:
                return expr
        elif isList(expr):
            if len(expr) == 0:
                return expr
            evaled = [self._eval(e) for e in expr]
            f = car(evaled)
            args = cdr(evaled)
            return self._apply(f, args)
        else:
            raise ValueError('Cannot evaluate "%s"' % expr)

    def _apply(self, f, args):
        if callable(f):
            result = f(self, args)
            # print "_apply %s to %s = %s" % (f, args, result)
        else:
            result = cons(f, args)
            # print "_apply: not callable: %s " % (result)
        return result

    def _parse(self, string):
        return json.loads(string)

    def _env(self, args):
        if len(args) != 1:
            raise ValueError('env: expected 1 arg, have %s' % len(args))
        arg = car(args)
        if not isString(arg):
            raise ValueError('env: expected string, have "%s"' % arg)
        if arg not in self.env:
            raise ValueError('env: "%s" not defined' % arg)
        return self.env[arg]

    def _and(self, args):
        if len(args) < 2:
            raise ValueError('and: expected at least 2 args, have %s' % len(args))
        if not areBools(args):
            raise ValueError('and: expected bools, have "%s"' % i)
        return reduce(lambda x,y: x and y, args)

    def _or(self, args):
        if len(args) < 2:
            raise ValueError('or: expected at least 2 args, have %s' % len(args))
        if not areBools(args):
            raise ValueError('or: expected bools, have "%s"' % i)
        return reduce(lambda x,y: x or y, args)

    def _not(self, args):
        if len(args) != 1:
            raise ValueError('not: expected 1 arg, have %s' % len(args))
        arg = car(args)
        if not isBool(arg):
            raise ValueError('not: expected bool, have "%s"' % i)
        return not arg

    def _in(self, args):
        if len(args) < 2:
            raise ValueError('in: expected at least 2 args, have %s' % len(args))
        needle = car(args)
        haystack = cdr(args)
        if isList(haystack[0]):
            if len(haystack) != 1:
                raise ValueError('in: expected args as either a list or expanded arguments, not both')
            return needle in haystack[0]
        else:
            return needle in haystack

    def _eq(self, args):
        first = car(args)
        rest = cdr(args)
        return all([i == first and (type(i) == type(first) or areNumeric([first, i])) for i in rest])

    def _ne(self, args):
        return not self._eq(args)

    def _lt(self, args):
        if len(args) != 2:
            raise ValueError('<: expected 2 args, have %s' % len(args))
        if not areNumeric(args):
            raise ValueError('<: expected Ints, have %s' % args)
        return args[0] < args[1]

    def _gt(self, args):
        if len(args) != 2:
            raise ValueError('>: expected 2 args, have %s' % len(args))
        if not areNumeric(args):
            raise ValueError('>: expected Ints, have %s' % args)
        return args[0] > args[1]

    def _le(self, args):
        if len(args) != 2:
            raise ValueError('<=: expected 2 args, have %s' % len(args))
        if not areNumeric(args):
            raise ValueError('<=: expected Ints, have %s' % args)
        return args[0] <= args[1]

    def _ge(self, args):
        if len(args) != 2:
            raise ValueError('>=: expected 2 args, have %s' % len(args))
        if not areNumeric(args):
            raise ValueError('>=: expected Ints, have %s' % args)
        return args[0] >= args[1]
    
    _ops = {
        "env": _env,
        "and": _and,
        "or": _or,
        "not": _not,
        "in": _in,
        "=": _eq,
        "!=": _ne,
        "<": _lt,
        ">": _gt,
        "<=": _le,
        ">=": _ge
    }


def car(l):
    return l[0] if len(l) > 0 else None


def cdr(l):
    return l[1:]


def cons(i,l):
    return [i] + l


def isBool(x):
    return isinstance(x, bool)


def areBools(l):
    return reduce(lambda x,y: x and y, [isBool(i) for i in l])


def isInt(x):
    return isinstance(x, int) and not isinstance(x, bool)


def areInts(l):
    return reduce(lambda x,y: x and y, [isInt(i) for i in l])


def isFloat(x):
    return isinstance(x, float)


def areFloats(l):
    return reduce(lambda x,y: x and y, [isFloat(i) for i in l])


def isNumeric(x):
    return isInt(x) or isFloat(x)


def areNumeric(l):
    return reduce(lambda x,y: x and y, [isNumeric(i) for i in l])


def isString(x):
    return isinstance(x, basestring)


def isList(x):
    return isinstance(x, list)


def test():
    assert car([]) == None
    assert car([1]) == 1
    assert car([1,2,3]) == 1

    assert cdr([]) == []
    assert cdr([1]) == []
    assert cdr([1,2]) == [2]
    assert cdr([1,2,3]) == [2,3]

    assert cons(1, []) == [1]
    assert cons(1, [2]) == [1,2]
    assert cons(1, [2,3]) == [1,2,3]

    assert isBool(True) == True
    assert isBool(1) == False
    assert isBool(1.0) == False
    assert isBool("hello") == False

    assert areBools([True]) == True
    assert areBools([True, False]) == True
    assert areBools([True, 1]) == False
    assert areBools([True, "hello"]) == False

    assert isInt(1) == True
    assert isInt(1.0) == False
    assert isInt(True) == False
    assert isInt("hello") == False

    assert isFloat(1.0) == True
    assert isFloat(1) == False
    assert isFloat(True) == False
    assert isFloat("hello") == False

    assert isNumeric(1) == True
    assert isNumeric(1.0) == True
    assert isNumeric(True) == False
    assert isNumeric("hello") == False

    assert isString("hello") == True
    assert isString(1) == False
    assert isString(True) == False

    assert isList([1,2,3]) == True
    assert isList(True) == False
    assert isList(1) == False
    assert isList("hello") == False

    vm = FlispVM()
    assert vm.eval_str("true") == True
    assert vm.eval_str("false") == False

    assert vm.eval_str('["and", true, true]') == True
    assert vm.eval_str('["and", true, false]') == False
    assert vm.eval_str('["and", true, true, true]') == True
    assert vm.eval_str('["and", ["and", true, true], true]') == True
    assert vm.eval_str('["or", true, false]') == True
    assert vm.eval_str('["or", false, false]') == False
    assert vm.eval_str('["or", true, true, true]') == True
    assert vm.eval_str('["or", ["or", true, true], true]') == True
    assert vm.eval_str('["and", ["or", false, true], ["or", true, false]]') == True

    assert vm.eval_str('["not", true]') == False
    assert vm.eval_str('["not", false]') == True
    assert vm.eval_str('["not", ["and", true, false]]') == True
    assert vm.eval_str('["not", ["and", true, true]]') == False

    assert vm.eval_str('["in", "a", "a", "b"]') == True
    assert vm.eval_str('["in", "a", "b", "b"]') == False
    assert vm.eval_str('["in", "a", ["a", "b"]]') == True
    assert vm.eval_str('["in", "a", ["b", "b"]]') == False
    assert vm.eval_str('["in", true, [true, 1, "hello"]]') == True
    assert vm.eval_str('["in", false, [true, 1, "hello"]]') == False
    assert vm.eval_str('["in", 1, [true, 1, "hello"]]') == True
    assert vm.eval_str('["in", 2, [true, 1, "hello"]]') == False
    assert vm.eval_str('["in", "hello", [true, 1, "hello"]]') == True
    assert vm.eval_str('["in", "world", [true, 1, "hello"]]') == False

    assert vm.eval_str('["=", 1, 1]') == True
    assert vm.eval_str('["=", 1, 2]') == False
    assert vm.eval_str('["=", 2, 2, 2, 2]') == True
    assert vm.eval_str('["=", true, true]') == True
    assert vm.eval_str('["=", true, false]') == False
    assert vm.eval_str('["=", true, 1]') == False
    assert vm.eval_str('["=", false, 0]') == False
    assert vm.eval_str('["=", "1", 1]') == False
    assert vm.eval_str('["=", "hello", "hello"]') == True
    assert vm.eval_str('["=", "hello", "world"]') == False
    assert vm.eval_str('["=", 1.0, 1.0]') == True
    assert vm.eval_str('["=", 1.0, 1.0000000]') == True
    assert vm.eval_str('["=", 1.0, 1.1]') == False
    assert vm.eval_str('["=", 1, 1.0]') == True
    assert vm.eval_str('["=", 1, 1.000000000000001]') == False
    assert vm.eval_str('["=", 1, 1.0000000000000001]') == True

    assert vm.eval_str('["!=", 1, 2]') == True
    assert vm.eval_str('["!=", 1, 1]') == False

    assert vm.eval_str('["<", 1, 2]') == True
    assert vm.eval_str('["<", 1, 1]') == False
    assert vm.eval_str('["<", 1, 0]') == False
    assert vm.eval_str('["<", -1, 1]') == True
    assert vm.eval_str('["<", -1, 0]') == True
    assert vm.eval_str('["<", -2, -1]') == True
    assert vm.eval_str('["<", 1.0, 1.1]') == True
    assert vm.eval_str('["<", 1.0, 1.0]') == False
    assert vm.eval_str('["<", 1, 1.1]') == True
    assert vm.eval_str('["<", 1, 1.0]') == False

    assert vm.eval_str('[">", 2, 1]') == True
    assert vm.eval_str('[">", 1, 1]') == False
    assert vm.eval_str('[">", 0, 1]') == False
    assert vm.eval_str('[">", 1, -1]') == True
    assert vm.eval_str('[">", 0, -1]') == True
    assert vm.eval_str('[">", -1, -2]') == True
    assert vm.eval_str('[">", 1.1, 1.0]') == True
    assert vm.eval_str('[">", 1.0, 1.0]') == False
    assert vm.eval_str('[">", 1.1, 1]') == True
    assert vm.eval_str('[">", 1.0, 1]') == False

    assert vm.eval_str('["<=", 1, 2]') == True
    assert vm.eval_str('["<=", 1, 1]') == True
    assert vm.eval_str('["<=", 1, 0]') == False
    assert vm.eval_str('["<=", 1.0, 1.1]') == True
    assert vm.eval_str('["<=", 1.0, 1.0]') == True
    assert vm.eval_str('["<=", 1.0, 0.9]') == False
    assert vm.eval_str('["<=", 1, 1.1]') == True
    assert vm.eval_str('["<=", 1, 1.0]') == True
    assert vm.eval_str('["<=", 1, 0.9]') == False

    assert vm.eval_str('[">=", 2, 1]') == True
    assert vm.eval_str('[">=", 1, 1]') == True
    assert vm.eval_str('[">=", 0, 1]') == False
    assert vm.eval_str('[">=", 1.1, 1.0]') == True
    assert vm.eval_str('[">=", 1.0, 1.0]') == True
    assert vm.eval_str('[">=", 0.9, 1.0]') == False
    assert vm.eval_str('[">=", 1.1, 1]') == True
    assert vm.eval_str('[">=", 1.0, 1]') == True
    assert vm.eval_str('[">=", 0.9, 1]') == False

    vm.env = {"user.isPremium": True}
    assert vm.eval_str('["env", "user.isPremium"]') == True
    assert vm.eval_str('"$user.isPremium"') == True
    assert vm.eval_str('["not", ["env", "user.isPremium"]]') == False
    assert vm.eval_str('["not", "$user.isPremium"]') == False

    vm.env = {"user.isPremium": True, "user.isLoggedIn": False}
    assert vm.eval_str('["and", ["env", "user.isPremium"], ["not", ["env", "user.isLoggedIn"]]]') == True
    assert vm.eval_str('["and", "$user.isPremium", ["not", "$user.isLoggedIn"]]') == True

    vm.env = {"user.isPremium": True, "user.sessionCount": 4}
    assert vm.eval_str('["and", ["env", "user.isPremium"], [">=", ["env", "user.sessionCount"], 4]]') == True
    assert vm.eval_str('["and", "$user.isPremium", [">=", "$user.sessionCount", 4]]') == True

    print "all tests passed."


if __name__ == "__main__":
    test()