Add cool function

1 files changed, 169 insertions, 0 deletions

diff --git a/backend/main.py b/backend/main.py
new file mode 100644
index 0000000..6cbea83
--- /dev/null
+++ b/backend/main.py
@@ -0,0 +1,169 @@
+from fastapi import FastAPI
+from fastapi.middleware.cors import CORSMiddleware
+import random
+from copy import deepcopy
+
+app = FastAPI(
+    title="Lambda Calculus",
+)
+
+app.add_middleware(
+    CORSMiddleware,
+    allow_origins=["*"],
+    allow_credentials=True,
+    allow_methods=["*"],
+    allow_headers=["*"],
+)
+
+LAMBDA = "\u03BB"
+
+class LambdaExpression:
+    def __init__(self):
+        pass
+
+    def evaluate(self, x):
+        return x
+    
+    def __str__(self):
+        pass
+    
+class Application(LambdaExpression):
+    def __init__(self, exp1, exp2):
+        self.exp1 = exp1
+        self.exp2 = exp2
+
+    def evaluate(self, x):
+        return super().evaluate(x)
+    
+    def __str__(self):
+        return f"({self.exp1}{self.exp2})" if type(self.exp2) == Variable else f"{self.exp1}{self.exp2}"
+
+    def __repr__(self) -> str:
+        return f"Application({repr(self.exp1)}, {repr(self.exp2)})"
+
+    
+class Variable(LambdaExpression):
+    def __init__(self, value):
+        self.value = value
+    
+    def evaluate(self, x):
+        return Variable(x)
+    
+    def __str__(self):
+        return self.value
+
+    def __repr__(self) -> str:
+        return f"Variable({repr(self.value)})"
+    
+class Abstraction(LambdaExpression):
+    def __init__(self, value, exp):
+        self.value = value
+        self.exp = exp
+
+    def evaluate(self, x):
+        return Abstraction(self.value, self.exp.evaluate(x))
+    
+    def __str__(self):
+        return f"{LAMBDA}{self.value}.{self.exp}"
+
+    def __repr__(self) -> str:
+        return f"Abstraction({repr(self.value)}, {repr(self.exp)})"
+
+def preform_bidmas(expression:str) -> list[str]:
+
+    expression = expression.replace(")", "\"],\"")
+    expression = expression.replace("(", "\",[\"")
+    expression = expression[2:-2]
+    expression = expression.replace("\"\",", "")
+    expression = expression.replace(",\"\"", "")
+    expression = eval(expression)
+
+    return expression
+    
+
+def parse_expression(expression_list: list[str]) -> LambdaExpression:
+    if len(expression_list) == 1 and len(expression_list[0]) == 1:
+        expression_list = expression_list[0]
+    if LAMBDA in expression_list[0]:
+        value, *exp = expression_list[0][1:].split(".")
+        exp = ".".join(exp)
+        return Abstraction(value, parse_expression([exp]))
+    if len(expression_list) == 1:
+        if len(expression_list[0]) == 1:
+
+            return Variable(expression_list[0][0])
+        elif type(expression_list) == str:
+            if LAMBDA in expression_list:
+                value, *exp = expression_list[1:].split(".")
+                exp = ".".join(exp)
+                return Abstraction(value, parse_expression([exp]))
+
+            return parse_expression(expression_list.split(""))
+        else:
+            return parse_expression(expression_list[0])
+
+
+    return Application(parse_expression(expression_list[:-1]), parse_expression(expression_list[-1]))
+
+def beta_reduction(expression: LambdaExpression) -> LambdaExpression:
+    def _substitute(expression: LambdaExpression, value: str, exp: LambdaExpression) -> LambdaExpression:
+        if type(expression) == Variable:
+            if expression.value == value:
+                return exp
+            else:
+                return expression
+        elif type(expression) == Application:
+            return Application(_substitute(expression.exp1, value, exp), _substitute(expression.exp2, value, exp))
+        elif type(expression) == Abstraction:
+            if expression.value == value:
+                return expression
+            else:
+                return Abstraction(expression.value, _substitute(expression.exp, value, exp))
+    # base case
+    if type(expression) == Variable:
+        return expression
+    elif type(expression) == Application:
+        if type(expression.exp1) == Abstraction:
+            return _substitute(expression.exp1.exp, expression.exp1.value, expression.exp2)
+        else:
+            return Application(beta_reduction(expression.exp1), beta_reduction(expression.exp2))
+    elif type(expression) == Abstraction:
+        return Abstraction(expression.value, beta_reduction(expression.exp))
+
+def free_variables(max_length) -> chr:
+    for i in range(97, 123):
+        yield chr(i)
+
+vars = free_variables(5)
+
+def random_lambda_expression(depth: int, set_free_variables: set[chr]) -> LambdaExpression:
+    if depth == 0:
+        return Variable(random.choice(set_free_variables))
+    else:
+        if random.random() < 0.3:
+            return Variable(random.choice(set_free_variables))
+        elif random.random() < 0.8:
+            return Application(random_lambda_expression(depth-1, set_free_variables), random_lambda_expression(depth-1, set_free_variables))
+        else:
+            new_free_variable = random.choice(set_free_variables)
+            return Abstraction(new_free_variable, random_lambda_expression(depth-1, set_free_variables))
+        
+def get_beta_steps(expression: LambdaExpression, steps: int) -> LambdaExpression:
+    expressions = [str(expression)]
+    for i in range(steps):
+        expression = beta_reduction(expression)
+        expressions.append(str(expression))
+    return expressions
+
+@app.post("/evaluate")
+async def evaluate(expression: str):
+    expression_list = preform_bidmas(expression)
+    expression = parse_expression(expression_list)
+    for i in range(100):
+        expression = beta_reduction(expression)
+    return {"expression": str(expression)}
+
+@app.get("/random")
+async def random_expression():
+    expression = random_lambda_expression(10, [chr(i) for i in range(97, 123)][:5])
+    return {"steps": get_beta_steps(expression, 4), "expression": str(expression)}
\ No newline at end of file