# Pythonic Perversities: the Guido taunts - part I
# Parser Combinators in Python - for shits and giggles, but mostly for shits.
#
# ``We deployed this lib on our prod server. Picture of cat.'' - codinghorror.com
# ``I am literally on it this time. This stuff is hot'' - joelonsoftware.com
# ``We use it to open the pod bay doors.'' - anonymous blogger

# The author of this grand work accepts donations and is also available for 
# Python related consulting and coding jobs. He's expensive though and currently running
# from the government for a crime he didn't commit (allegedly he used an catamorphism in public -- 
# I know this is something he would never condone), but he will lambda your shit up if you can find him.

# Features:
#   Uses nested lambdas to simulate currying and laziness (OOOH YEAH!)
#   Uses nested ternary operators and list comprehensions to be able to write everything as a lambda (IT'S SHORTER)
#   Can ostensibly be used to write context free and context dependent grammars
#   Gives strange non-descriptive errors that you won't see using conventional Python, making it hard to write context free and context dependent grammars
#   Only suitable for real programmers

import operator

satisfy = lambda charToBool: lambda text: ([(text[0], text[1:])] 
                                           if charToBool(text[0]) else []) if text != "" else []

isChar = lambda c: satisfy(lambda x: c == x)
letter = satisfy( str.isalpha)
digit = satisfy(str.isdigit)
alphanumeric = satisfy(str.isalnum)
token = lambda token: lambda text: [(token, text[len(token):])] if token == text[:len(token)] else []

comb = lambda parser1, parser2: lambda text: [ (v1(v2), t2) 
                                              for v1, t1 in parser1(text) 
                                              for v2, t2 in parser2(t1)]

choice = lambda parser1, parser2: lambda text: parser1(text) + parser2(text)

# Extra combinators
just = lambda parser: lambda text: [ (v, "") for (v, t) in parser(text) if t == "" ]
succeed = lambda value: lambda text: [ (value, text) ]
option = lambda parser, value: choice(parser, succeed(value))
fail = lambda parser: lambda text: []
mapp = lambda f, parser: lambda text: [ ( f(v), t ) for v, t in parser(text) ]
anyp = lambda plist: lambda text: [ v for p in plist for v in p(text) if v != [] ]
parse = lambda parser, text: just(parser)(text)

# holy shit -- lazy evaluation!
many = lambda parser: option(comb(mapp(lambda a: lambda b: [a] + b, parser), lambda x: many(parser)(x)), [])
many1 = lambda parser: comb(mapp(lambda a: lambda b: [a] + b, parser), many(parser))

# extras for characters; automatically flatten list (ie. concatenate, dumbledoremorphism)
concat = lambda xs: reduce(operator.add, xs, "")
manyc = lambda parser: mapp(concat, many(parser))
many1c = lambda parser: mapp(concat, many1(parser))

# Some helper functions for my new language that will soon take over the world by storm.
integer = many1(digit)
whitespace = many1c(satisfy(str.isspace))
space = many1c(isChar(" "))


# Example: counting highest matching parentheses - 
# IT'S CRAZY INTUITIVE!
parens = lambda text: choice( comb(comb(comb(mapp(lambda x: lambda h1: lambda y: lambda  h2: max(1+h1, h2), isChar("(")), parens), isChar(")")), parens) , succeed(0))(text)
print parse(parens, "()((()))")


# Here's a bigger tree generating parser. I know you want it.

class ParseTree:
        def __init__(self, value):
                self.value = value
        def __str__(self):
                return "%s {%s}" % (self.__class__.__name__, self.value)
        def __repr__(self):
                return str(self)

class Identifier(ParseTree): pass
class IdentifierList(ParseTree): pass
class Operator(ParseTree): pass
class Lambda(ParseTree): pass
class Expression(ParseTree): pass
class ApplyOperator(ParseTree): pass
class ApplyFunction(ParseTree): pass
class Program(ParseTree): pass


spacepad = lambda parser: choice( comb(mapp( lambda a: lambda b: b, whitespace), parser), parser)
spacepad1 = lambda parser: comb(mapp( lambda a: lambda b: b, whitespace), parser)
ident = comb(mapp(lambda a: lambda b: Identifier(a + b), spacepad(letter)), manyc(alphanumeric))

identlist = comb(mapp(lambda a: lambda b: IdentifierList([a] + b), ident), 
                 many(comb(mapp(lambda a: lambda b: b, whitespace),ident)))
funcapply = comb(mapp(lambda a: lambda b: ApplyFunction([a] + b), ident), 
                many1(spacepad1(ident)))

simple_expr = anyp([ident, funcapply])
compound_expr = anyp([simple_expr, lambda text: operapply(text)])
expr = anyp([lambda text: _lambda(text), compound_expr])
program = comb(comb(mapp(lambda a: lambda b: lambda c: Program([a] + b), expr), 
               many(comb(mapp(lambda a: lambda b: b, isChar(";")), expr))), many(satisfy(str.isspace)))


oper = mapp(Operator, spacepad(many1c(anyp(map(isChar, ["=", "-", "|", "!", "<", ">", "$", "+", "/"])))))
operapply = comb(comb(mapp(lambda a: lambda o: lambda b: ApplyOperator([a, o, b]), 
                           simple_expr), oper), compound_expr)



_lambda = comb(comb(comb(mapp(lambda a: lambda idents: lambda c: lambda exp: 
                              Lambda([idents,exp]), spacepad(isChar('\\'))), identlist),
                    spacepad(token("->"))), expr)

print parse(program, """

            \\ a b -> a + b + c; 
            b
            
            """)

[(3, '')]
[(Program {[Lambda {[IdentifierList {[Identifier {a}, Identifier {b}]}, ApplyOperator {[Identifier {a}, Operator {+}, ApplyOperator {[Identifier {b}, Operator {+}, Identifier {c}]}]}]}, Identifier {b}]}, '')]