Skip to content

Instantly share code, notes, and snippets.

@cellularmitosis cellularmitosis/README.md
Last active Oct 19, 2019

Embed
What would you like to do?
flisp.py: a simple predicate evaluator

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.

#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.