# -*- coding: utf-8 -*-
#
# Polynomix interpreter
LAST_MODIFIED="Jul. 2nd 2026 14:35 UTC+8";VERSION="1.0.0"
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#                                                                           #
#  Copyright 2026 islptng                                                   #
#                                                                           #
#  Licensed under the Apache License, Version 2.0 (the "License");          #
#  you may not use this file except in compliance with the License.         #
#  You may obtain a copy of the License at                                  #
#                                                                           #
#      http://www.apache.org/licenses/LICENSE-2.0                           #
#                                                                           #
#  Unless required by applicable law or agreed to in writing, software      #
#  distributed under the License is distributed on an "AS IS" BASIS,        #
#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #
#  See the License for the specific language governing permissions and      #
#  limitations under the License.                                           #
#                                                                           #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

from sys import argv
from math import gcd, lcm, floor, isinf, isnan
from random import randint, sample
import os
from time import sleep, time

def _(): yield None
Generator = type(_())

class PolyError(Exception):
	def __init__(self, msg, pos=None, AlreadyPoly = False):
		if pos == None: pos = []
		if not AlreadyPoly: super().__init__(List(msg), pos)
		else: super().__init__(msg, pos)

class Inst:
	PUSH = 0 # val
	DROP = 1 # index
	TAKE = 2 # index
	DUP = 3 # index
	INSERT = 4 # index
	DEFINE = 5 # name
	GET = 6 # name
	SET = 7 # name
	APPLY = 8 # arity
	CONSITER = 9 # rank
	LOADLAMBDA = 10 # types, body, closurepos
	ENTERSCOPE = 11 # /
	EXITSCOPE = 12 # /
	CLOSURE = 13 # name / name, value
	JMP = 14 # ptr
	JF = 16 # ptr
	RETURN = 17 # level, res
	TRY = 19 # exceptptr
	EXCEPT = 20 # endptr
	RAISE = 21 # name
	RECUR = 22 # level
	PUSHMARK = 23 # /
	CONSLIST = 24 # /
	CONSPAIR = 25 # /
	EXPANDPAIR = 26 # /
	EXPANDLIST = 27 # prefn,postfn / length
	CONSSTRUCT = 28 # / (destruct) / name (construct)
	COMMUTE = 29 # index
	CONSTRAIN = 30 # arity
	EVAL = 128 # /

class Expr:
	def __init__(self, num = 0, den = 1):
		self.num = num
		self.den = den
		self.simplify()
	def simplify(self):
		if self.den == 0:
			if self.num: self.num = 1 # -Inf = Inf on a Riemann sphere
		else:
			gcdn = gcd(self.num, self.den)
			if self.den < 0: gcdn *= -1
			self.num //= gcdn
			self.den //= gcdn
	def __add__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Addition with invalid type.", [])
		return Expr(self.num * other.den + other.num * self.den, self.den * other.den)
	def __sub__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Subtraction with invalid type.", [])
		return Expr(self.num * other.den - other.num * self.den, self.den * other.den)
	def __neg__(self): return Expr(-self.num, self.den)
	def __mul__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Multiplication with invalid type.", [])
		return Expr(self.num * other.num, self.den * other.den)
	def __truediv__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Division with invalid type.", [])
		return Expr(self.num * other.den, self.den * other.num)
	def __floordiv__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Floor division with invalid type.", [])
		divisor = self.den * other.num
		if divisor == 0: return Expr(0, 0) # NaN
		return Expr((self.num * other.den) // divisor, 1)
	def __mod__(self, other):
		if not isinstance(other, Expr): raise PolyError("TypeError| Modulus with invalid type.", [])
		divisor = other.num * self.den
		if divisor == 0: return Expr(0, 0) # NaN
		return Expr(self.num * other.den % divisor, self.den * other.den)
	def __eq__(self, other):
		if not isinstance(other, Expr): return False
		return self.num == other.num and self.den == other.den
	__ne__ = lambda self,other: not self.__eq__(other)
	def __hash__(self):
		return hash(("Expr", self.num, self.den))
	def __bool__(self): return self.num != 0
	def __str__(self):
		if self.den == 0: return "Infinity" if self.num else "NaN"
		if self.den == 1: return str(self.num)
		return f"{self.num}/{self.den}"
	# __str__ is directly used in Polynomix str.

	__repr__ = lambda self: f"Poly<{str(self)}>"
	# __repr__ are for Python debugging. For Polynomix repr, there'll be another function.

class Null:
	def __init__(self): pass
	def __hash__(self): return hash(None)
	def __bool__(self): return False
	def __str__(self): return "\\;"
	__repr__ = lambda self: "Poly<Null>"
	__eq__ = lambda self,other: isinstance(other, Null)
	__ne__ = lambda self,other: not isinstance(other, Null)
NULL = Null()

class Bool:
	def __init__(self, val): self.val = bool(val)
	def __hash__(self): return hash(self.val)
	def __bool__(self): return self.val
	def __str__(self): return "True" if self.val else "False"
	__repr__ = lambda self: f"Poly<{self.val}>"
	def __neg__(self): return Bool(not self.val)

class Char:
	def __init__(self, val):
		if isinstance(val, str):
			if len(val) > 1:
				raise Exception("Char can only be initialized with a single character.")
			self.val = val
		else: self.val = chr(int(val))
	__eq__ = lambda self,other: isinstance(other, Char) and self.val == other.val
	__ne__ = lambda self,other: not isinstance(other, Char) or self.val != other.val
	__bool__ = lambda self: True
	__hash__ = lambda self: hash(self.val)
	__str__ = lambda self: self.val
	__repr__ = lambda self: f"Poly<{repr(self.val)}>"


class List:
	def __init__(self,s=[]):
		if isinstance(s,str):
			r = []
			for i in list(s):
				r.append(Char(i))
			self.val = list(r)
		else: self.val = list(s)
	def __len__(self): return len(self.val)
	def __getitem__(self, index):
		try:
			if isinstance(index,Pair):
				if isinstance(index.former,Null) and isinstance(index.latter,Null): return self
				if isinstance(index.former,Null) and isinstance(index.latter,Expr):
					if index.latter.den != 1: raise PolyError("Index must be integer", [])
					return List(self.val[:index.latter.num])
				if isinstance(index.latter,Null) and isinstance(index.former,Expr):
					if index.former.den != 1: raise PolyError("Index must be integer", [])
					return List(self.val[index.former.num:])
				if isinstance(index.former,Expr) and isinstance(index.latter,Expr):
					if index.former.den != 1: raise PolyError("Index must be integer", [])
					if index.latter.den != 1: raise PolyError("Index must be integer", [])
					return List(self.val[index.former.num:index.latter.num])
				raise PolyError("ValueError| Invalid slice.", [])
			if isinstance(index,List): return self[index.val[0]][List(index.val[1:])] if len(index) > 1 else self[index.val[0]]
			if isinstance(index,Expr):
				if index.den != 1: raise PolyError("Index must be integer", [])
				return self.val[index.num]
			return self.val[index]
		except (IndexError, TypeError): raise PolyError("ValueError| Index out of range.", [])
	def setitem(self, index, value):
		try:
			if isinstance(index,Pair):
				if not isinstance(value, List): raise PolyError("TypeError| Cannot replace a slice with a non-list.", [])
				if isinstance(index.former,Null) and isinstance(index.latter,Null): return value
				if isinstance(index.former,Null) and isinstance(index.latter,Expr):
					if index.latter.den != 1: raise PolyError("Index must be integer", [])
					return List(value.val + self.val[index.latter.num:])
				if isinstance(index.latter,Null) and isinstance(index.former,Expr):
					if index.former.den != 1: raise PolyError("Index must be integer", [])
					return List(self.val[:index.former.num] + value.val)
				if isinstance(index.former,Expr) and isinstance(index.latter,Expr):
					if index.former.den != 1: raise PolyError("Index must be integer", [])
					if index.latter.den != 1: raise PolyError("Index must be integer", [])
					return List(self.val[:index.former.num] + value.val + self.val[index.latter.num:])
				raise PolyError("ValueError| Invalid slice.", [])
			if isinstance(index,List):
				if not index.val: return value
				if len(index.val) == 1: return self.setitem(index.val[0], value)
				sub = self[index.val[0]]
				if not (isinstance(sub, List) or isinstance(sub, Pair)):
					raise PolyError("TypeError| Cannot replace a non-list with a list.", [])
				return self.setitem(index.val[0], sub.setitem(List(index.val[1:]), value))
			if isinstance(index,Expr):
				if index.den != 1: raise PolyError("Index must be integer", [])
				return List(self.val[:index.num] + [value] + (self.val[index.num+1:] if index.num != -1 else []))
		except (IndexError, TypeError): raise PolyError("ValueError| Index out of range.", [])
	def __eq__(self, other):
		if not isinstance(other, List):
			return False
		return self.val == other.val
	__int__ = __len__
	def __str__(self):
		for i in self.val:
			if not isinstance(i, Char): return "[%s]" % " ".join([str(_) for _ in self.val])
		return "".join([_.val for _ in self.val])
	def __repr__(self):
		for i in self.val:
			if not isinstance(i, Char): return f"Poly<{repr(self.val)}>"
		return f"Poly<Str:{repr(str(self))}>"
	def __add__(self, other):
		if not isinstance(other, List): raise PolyError("TypeError| Cannot add a non-list to a list.", [])
		return List(self.val + other.val)
	def __neg__(self): return List(self.val[::-1]) # Duck typing
	__hash__ = lambda self: hash(tuple(self.val))
	__bool__ = lambda self: len(self.val) != 0
def Zip(arg):
	try:
		if isinstance(arg, List):
			if len(arg) == 0: return List()
			res = [[] for _ in range(len(arg[0]))]
			for i in arg.val:
				for j in range(len(i)):
					res[j]=res[j]+[i.val[j]]
			return List([List(x) for x in res])
		elif isinstance(arg, Pair):
			if len(arg.former) != len(arg.latter): raise PolyError("ValueError| Different lengths when zipping.", [])
			res = []
			for i in range(len(arg.former)):
				res.append(Pair(arg.former.val[i],arg.latter.val[i]))
			return List(res)
	except IndexError: raise PolyError("ValueError| Different lengths when zipping.", [])
class Pair:
	def __init__(self, former, latter):
		self.former = former
		self.latter = latter
	def __getitem__(self, index):
		if isinstance(index, List):
			try: return self[index.val[0]][List(index.val[1:])] if len(index) > 1 else self[index.val[0]]
			except (IndexError, TypeError): raise PolyError("ValueError| Index out of range.", [])
		return self.latter if index else self.former # boolean index, only used for broadcasting and / (dyadic) operator
	def setitem(self, index, value):
		if isinstance(index, List):
			try:
				if not index.val: return value
				if len(index.val) == 1: return self.setitem(index.val[0], value)
				sub = self[index.val[0]]
				if not (isinstance(sub, List) or isinstance(sub, Pair)):
					raise PolyError("TypeError| Cannot replace a non-list with a list.", [])
				return self.setitem(index.val[0], sub.setitem(List(index.val[1:]), value))
			except (IndexError, TypeError): raise PolyError("ValueError| Index out of range.", [])
		return Pair(self.former,value) if index else Pair(value,self.latter)
	def __len__(self): return 2 # only used for broadcasting
	def __neg__(self): return Pair(self.latter, self.former) # only used for / (monadic) operator
	def __str__(self):
		return "(%s,%s)" % (str(self.former), str(self.latter))
	def __repr__(self): return f"Poly<({repr(self.former)},{repr(self.latter)})>"
	__eq__ = lambda self,other: isinstance(other, Pair) and self.former == other.former and self.latter == other.latter
	__ne__ = lambda self,other: not isinstance(other, Pair) or self.former != other.former or self.latter != other.latter
	__hash__ = lambda self: hash(("Pair",self.former,self.latter))
	__bool__ = lambda self: bool(self.former) and bool(self.latter)
class UserDefinedTypeObject:
	def __init__(self, type, value):
		self.type = type
		self.value = value
	__str__ = lambda self: "<%s: %s>" % (self.type, self.value)
	__repr__ = lambda self: "Poly<%s %s>" % (self.value, self.type)
	__hash__ = lambda self: hash((self.type,self.value))
	__eq__ = lambda self,other: isinstance(other, UserDefinedTypeObject) and self.type == other.type and self.value == other.value
	__ne__ = lambda self,other: not isinstance(other, UserDefinedTypeObject) or self.type != other.type or self.value != other.value
class Func:
	__str__ = lambda self: "(\u03bb)" # U+03BB is lambda
class BasicFunc(Func):
	def __init__(self, overloads=None, name=None): self.overloads = [] if overloads is None else overloads; self.name = name
	def config(self, args, body):
		self.overloads.append((args, body))
	def __add__(self, other):
		if isinstance(other, BasicFunc): return BasicFunc(self.overloads + other.overloads, self.name or other.name)
		else: return BasicFunc(self.overloads + [other], self.name)
	def __radd__(self, other): return BasicFunc([other] + self.overloads, self.name)
	def get(self, args):
		for finst in self.overloads:
			if not isinstance(finst, tuple):
				res = finst.get(args)
				if res is not None: return res
			else:
				argstype, body = finst
				if not argstype: return body
				if len(argstype) != len(args): continue
				flag = True
				for t,i in zip(argstype, args):
					if not t.match(i): flag = False; break
				if flag: return body
		return None
	__hash__ = lambda self: id(self)
	__repr__ = lambda self: "PolyFunction"
	__eq__ = lambda self,other: isinstance(other, BasicFunc) and self.overloads == other.overloads
	__ne__ = lambda self,other: not isinstance(other, BasicFunc) or self.overloads != other.overloads
class CommutedFunc(Func):
	def __init__(self, basis, cmindex=1):
		self.basis = basis
		self.index = cmindex
	def __add__(self, other):
		if not isinstance(other, BasicFunc): return BasicFunc([self, other])
		return other.__radd__(self)
	def get(self, args):
		args = list(args)
		arity = len(args)
		if self.index < arity: args[0], args[self.index] = args[self.index], args[0]
		else:
			if arity != 1: return None
			args = args*(self.index+1)
		res = self.basis.get(args)
		if res is None: return None
		if isinstance(res,list):
			if arity == 1: res = [(Inst.DUP, "<commuted>", 1)] * (self.index) + res
			else:
				swap_ops = [
					(Inst.TAKE, "<commuted>", arity - self.index),
					(Inst.INSERT, "<commuted>", arity),
					(Inst.TAKE, "<commuted>", arity - 1)
				]
				if self.index < arity - 1:
					swap_ops.append((Inst.INSERT, "<commuted>", arity - 1 - self.index))
				res = swap_ops + res
			return res
		if arity == 1: return lambda arg: res(*([arg]*(self.index+1)))
		def wrapper(*args):
			args = list(args)
			args[0], args[self.index] = args[self.index], args[0]
			return res(*args)
		return wrapper
	__hash__ = lambda self: hash(("Func2",self.index,self.basis))
	__repr__ = lambda self: "PolyFunction_Commute" * self.index
	__eq__ = lambda self,other: isinstance(other, CommutedFunc) and self.index == other.index and self.basis == other.basis
	__ne__ = lambda self,other: not isinstance(other, CommutedFunc) or self.index != other.index or self.basis != other.basis
class Train(Func):
	def __init__(self, bases):
		bases = list(bases)
		self.top = bases.pop(1)
		self.bases = bases
	def __add__(self, other):
		if not isinstance(other, BasicFunc): return Train([self, other])
		return other.__radd__(self)
	def get(self, args):
		arity = len(args)
		toparity = len(self.bases)
		res = []
		for i in range(toparity - 1):
			for j in range(arity): res.append((Inst.DUP, "<train>", arity + i))
			res.append((Inst.PUSH, "<train>", self.bases[i]))
			res.append((Inst.APPLY, "<train>", arity))
		for j in range(arity): res.append((Inst.TAKE, "<train>", arity + toparity - 1))
		res.append((Inst.PUSH, "<train>", self.bases[-1]))
		res.append((Inst.APPLY, "<train>", arity))
		res.append((Inst.PUSH, "<train>", self.top))
		res.append((Inst.APPLY, "<train>", toparity))
		return res
	__hash__ = lambda self: hash(("Func3",tuple(self.bases),self.top))
	__repr__ = lambda self: "PolyFunction_Train"
	__eq__ = lambda self,other: isinstance(other, Train) and self.top == other.top and self.bases == other.bases
	__ne__ = lambda self,other: not isinstance(other, Train) or self.top != other.top or self.bases != other.bases

class dIterator:
	def __init__(self,l,r):
		if isinstance(l,dIterator):
			self.l,self.r = l.l,l.r+r
		else: self.l,self.r = l,r
	__str__ = lambda self: str(self.l) + "it." + "-".join(str(i) for i in self.r)
	__repr__ = lambda self: repr(self.l) + "it." + "-".join(str(i) for i in self.r)

class CONT: pass

def _analyzeTypeStr(s):
	def _lexTypeStr(s):
		assert s[0] == "$" and s[-1] == "$", "TypeString must start and end with $."
		s=s[1:-1]
		# tokenization
		tok = []
		cur = ""
		for i in s:
			if i in "0123456789": cur += i
			elif i in "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" or ord(i) > 128:
				if cur.isnumeric():
					tok.append(cur)
					cur = i
				else: cur += i
			elif i == ".":
				if cur and cur.isnumeric():
					tok.append((".",cur))
					cur = ""
			elif i in ';="/+,[]>(){}|*':
				if cur:
					tok.append(cur)
					cur = ""
				tok.append(i)
			elif i in " \r\n\t":
				if cur:
					tok.append(cur)
					cur = ""
			else: raise PolyError("SyntaxError| Unexpected character in TypeString.", [])
		if cur: tok.append(cur)
		# nesting
		res = []
		stackp = []
		stackb = []
		braceIndex = 1
		braceIndices = []
		for i in tok:
			res.append(i)
			if i == "(":
				stackp.append(len(res)-1)
				stackb.append(0)
			elif i == ")":
				if len(stackp) == 0: raise PolyError("SyntaxError| Unmatched closing parenthesis in TypeString.", [])
				if stackb.pop() != 0: raise PolyError("SyntaxError| Unmatched closing parenthesis in TypeString.", [])
				ind = stackp.pop()
				res[ind:] = [("(", res[ind+1:-1])]
			elif i == "[":
				stackp.append(len(res)-1)
				stackb.append(1)
			elif i == "]":
				if len(stackp) == 0: raise PolyError("SyntaxError| Unmatched closing bracket in TypeString.", [])
				if stackb.pop() != 1: raise PolyError("SyntaxError| Unmatched closing bracket in TypeString.", [])
				ind = stackp.pop()
				res[ind:] = [("[", res[ind+1:-1])]
			elif i == "{":
				stackp.append(len(res)-1)
				stackb.append(2)
				braceIndices.append(braceIndex)
				braceIndex += 1
			elif i == "}":
				if len(stackp) == 0: raise PolyError("SyntaxError| Unmatched closing brace in TypeString.", [])
				if stackb.pop() != 2: raise PolyError("SyntaxError| Unmatched closing brace in TypeString.", [])
				ind = stackp.pop()
				res[ind:] = [("{", res[ind+1:-1], str(braceIndices.pop()))]
		if len(stackp) != 0:
			v = stackb.pop()
			if v == 1: raise PolyError("SyntaxError| Unmatched opening bracket in TypeString.", [])
			if v == 0: raise PolyError("SyntaxError| Unmatched opening parenthesis in TypeString.", [])
			if v == 2: raise PolyError("SyntaxError| Unmatched opening brace in TypeString.", [])
		return res
	def _parseTypeStr(tok):
		if len(tok) == 0: return ["*"]
		if "|" in tok:
			indices = [i for i,x in enumerate(tok) if x == "|"]+[None]
			res = ["|"]
			lastind = -1
			for i in indices:
				res += _parseTypeStr(tok[lastind+1:i])
				lastind = i
			return res
		if "," in tok:
			indices = [i for i,x in enumerate(tok) if x == ","]+[None]
			lastind = indices[0]
			res = _parseTypeStr(tok[:lastind])
			for i in indices[1:]:
				res = (",",res,_parseTypeStr(tok[lastind+1:i]))
				lastind = i
			return [res]
		if len(tok) >= 2: raise PolyError("SyntaxError| Too much objects in a TypeString.",[])
		if isinstance(tok[0],tuple):
			tok = list(tok[0])
			tok[1] = _parseTypeStr(tok[1])
			tok = [tuple(tok)]
		return tok
	def _optimizeAST(tsast):
		if isinstance(tsast, tuple):
			op = tsast[0]
			if op == "(": return _optimizeAST(tsast[1])
			if op == ",": return (",", _optimizeAST(tsast[1]), _optimizeAST(tsast[2]))
			if op == "[": return ("[", _optimizeAST(tsast[1]))
			if op == "{": return ("{", _optimizeAST(tsast[1]), tsast[2])
			if op == ".": return (".", _optimizeAST(tsast[1]))
		if isinstance(tsast, list):
			if len(tsast) == 1: return _optimizeAST(tsast[0])
			assert tsast[0] == "|"
			branches = tsast[1:]
			result = set()
			for i in branches:
				i = _optimizeAST(i)
				if isinstance(i, tuple) and i[0] == "|": result |= set(i[1:])
				else:
					if i == "*": return "*"
					result.add(i)
			if len(result) == 1: return result.pop()
			return ("|",) + tuple(result)
		return tsast
	return _optimizeAST(_parseTypeStr(_lexTypeStr(s)))
def _jtypeof(obj):
	if isinstance(obj, Null): return ";"
	if isinstance(obj, Bool): return "="
	if isinstance(obj, Char): return '"'
	if isinstance(obj, Type): return "/"
	if isinstance(obj, Expr): return "+"
	if isinstance(obj, Func): return ">"
	if isinstance(obj, Pair): return (",", _jtypeof(obj.former), _jtypeof(obj.latter))
	if isinstance(obj, List):
		types = set()
		for i in obj.val: types.add(_jtypeof(i))
		if len(types) == 1: return ("[", types.pop())
		return ("[", ("|",) + tuple(types))
	if isinstance(obj, UserDefinedTypeObject): return obj.type
	if isinstance(obj, dIterator): return _jtypeof(obj.l)
	raise TypeError("Unrecognized object for typeof: " + repr(obj))
stypeof = lambda obj: str(Type(_jtypeof(obj), analyze=False))

class Type:
	def __init__(self,t,analyze=True):
		if analyze:	self.val = _analyzeTypeStr(t)
		else: self.val = t
	def match(self, object):
		captureGroups = {}
		capturedTypes = {}
		def _match(tsast, obj, returnMatchedType=False):
			nonlocal captureGroups, capturedTypes
			if isinstance(tsast, str):
				if tsast == "*": return True
				if tsast == ";": return isinstance(obj, Null)
				if tsast == "=": return isinstance(obj, Bool)
				if tsast == '"': return isinstance(obj, Char)
				if tsast == "/": return isinstance(obj, Type)
				if tsast == "+": return isinstance(obj, Expr)
				if tsast == ">": return isinstance(obj, Func)
				if tsast.isdigit():
					if tsast not in captureGroups: raise PolyError("SyntaxError| Capture group referenced before matching in TypeString.", [])
					return _match(captureGroups[tsast], obj)
				return isinstance(obj, UserDefinedTypeObject) and obj.type == tsast
			elif isinstance(tsast, tuple):
				if tsast[0] == "(": return _match(tsast[1], obj, returnMatchedType)
				if tsast[0] == ",": return isinstance(obj, Pair) and _match(tsast[1], obj.former) and _match(tsast[2], obj.latter)
				if tsast[0] == "[":
					if not isinstance(obj, List): return False
					for i in obj.val:
						if not _match(tsast[1], i): return False
					return True
				if tsast[0] == "{":
					_, typ, groupIndex = tsast
					captureGroups[groupIndex] = typ
					res = _match(typ, obj, True)
					if res:
						if res is not True: capturedTypes[groupIndex] = res
						else: capturedTypes[groupIndex] = _jtypeof(obj)
						return True
					return False
				if tsast[0] == ".":
					if tsast[1] in captureGroups:
						return _match(captureGroups[tsast[1]], obj)
					else: raise PolyError("SyntaxError| Capture group referenced before matching in TypeString.", [])
				if tsast[0] == "|":
					for i in tsast[1:]:
						if _match(i, obj): return i if returnMatchedType else True
					return False
		return _match(self.val, object)
	def __str__(self):
		def recur(val, parent_prio):
			if isinstance(val, str):
				if val == "*": return ""
				return val
			if val[0] == "|":
				s = "|".join(recur(child, 1) for child in val[1:])
				if parent_prio > 1: return "(" + s + ")"
				return s
			if val[0] == ",":
				s = recur(val[1], 2) + "," + recur(val[2], 2 + 1)
				if parent_prio > 2: return "(" + s + ")"
				return s
			if val[0] == "[": return "[" + recur(val[1], 0) + "]"
			if val[0] == "{": return "{" + recur(val[1], 0) + "}"
			if val[0] == "(": return recur(val[1], 0)
			if val[0] == ".": return val[1] + "."
			return str(val)
		return "$" + (recur(self.val, 0) or "*") + "$"
	__repr__ = __str__
	__eq__ = lambda self,other: isinstance(other,Type) and self.val == other.val
	__ne__ = lambda self,other: not isinstance(other,Type) or self.val != other.val

def _wrapParen(st, enable): return "("+st+")" if enable else st
def PolyRepr(obj, withParen=False, returnVerb=False):
	if isinstance(obj,Expr):
		res = ("" if obj.num >= 0 else "\\") + str(abs(obj.num))
		if obj.den != 1:
			res += "/"+str(obj.den)
			return _wrapParen(res, withParen) +"!"*returnVerb
		return res
	if isinstance(obj,Null): return "\\;" +"!"*returnVerb
	if obj is CONT: return "(0?)" +"!"*returnVerb
	if isinstance(obj,Bool): return ("(1|)" if obj else "(0|)") +"!"*returnVerb
	if isinstance(obj,Char):
		escaped = {"\n":"\\n","\t":"\\t","\r":"\\r","\b":"\\b","`":"\\p","'":"\\q","\\":"\\\\","\0":"\\;"}
		return '"' + escaped.get(obj.val, obj.val) +"!"*returnVerb
	if isinstance(obj,List):
		if len(obj.val) == 0: return "[]" +"!"*returnVerb
		leftparenmiss = 0
		rightparenmiss = 0
		for i in obj.val:
			if not isinstance(i, Char): return "[%s]" % " ".join([PolyRepr(_) for _ in obj.val]) # No ambiguity, no parenthesis
			if i.val == "`": rightparenmiss += 1
			if i.val == "'":
				if rightparenmiss > 0: rightparenmiss -= 1
				else: leftparenmiss += 1
		if leftparenmiss == 0 and rightparenmiss == 0: return "`"+"".join([_.val for _ in obj.val])+"'" +"!"*returnVerb
		if leftparenmiss == 0:
			return _wrapParen("`"+"".join([_.val for _ in obj.val])+"'"*rightparenmiss+"'/(\\;,-"+str(rightparenmiss)+")", withParen) +"!"*returnVerb
		if rightparenmiss == 0:
			return _wrapParen("(`"+"`"*leftparenmiss+"".join([_.val for _ in obj.val])+("'/(%d,\\;))" % leftparenmiss), withParen) +"!"*returnVerb
		return _wrapParen("(`"+"`"*leftparenmiss+"".join([_.val for _ in obj.val])+"'"*rightparenmiss+("'/(%d,-%d))"%(leftparenmiss,rightparenmiss)), withParen) +"!"*returnVerb
	if isinstance(obj,Pair):
		return _wrapParen(PolyRepr(obj.former) + "," + PolyRepr(obj.latter, True), withParen) +"!"*returnVerb# (1,2,3) is ((1,2),3) ; not (1,(2,3))
	if isinstance(obj,UserDefinedTypeObject): return "(%s %s.)" % (obj.value, obj.type) +"!"*returnVerb
	if isinstance(obj,Type): return str(obj) +"!"*returnVerb
	# Train and commute
	if isinstance(obj,CommutedFunc):
		res = PolyRepr(obj.basis, withParen=True, returnVerb=returnVerb)
		return _wrapParen(res + "!!" * obj.index, withParen)
	if isinstance(obj,Train):
		lfork, *rfork = obj.bases
		top = PolyRepr(obj.top, withParen=True, returnVerb=True)
		left = PolyRepr(lfork, withParen=True, returnVerb=True)
		right = "".join([PolyRepr(_, withParen=True, returnVerb=True) for _ in rfork])
		return "{" + left + top + right + ("}" if returnVerb else "}!")
	if isinstance(obj,BasicFunc):
		if obj.name: return obj.name if returnVerb else obj.name + "!"
		val = obj.overloads
		if len(val) > 1: return _wrapParen("+".join([PolyRepr(BasicFunc([_]),withParen=True) for _ in val])) + ("!" if returnVerb else "")
		types, body = val[0]
		argnames = []
		cnt = 0
		for i in body[1:]: # Skip ENTERSCOPE at the beginning
			if i[0] == Inst.DEFINE: argnames.append(i[2]); cnt += 1
			else: break
		body = body[cnt+1:-1] # Remove arguments and EXITSCOPE at the end
		res = "("
		flag = False
		for a,t in zip(reversed(argnames),types):
			if not a:
				flag = True
				break
			res += a + (str(t) if t != Type("$*$") else "") + " "
		if flag: res = "("
		else: res = res[:-1] + ">"
		return res + "\u03bb)" +"!"*returnVerb
	
	if isinstance(obj,dIterator): return "".join("\\"+"!"*i for i in reversed(obj.r)) + PolyRepr(obj.l) + "!"*returnVerb

# Null < Bool < Char < Expr < Type < Pair < List < CommutedFunc < Train < BasicFunc
_Comparison = {Null:0, Bool:1, Char:2, Expr:3, Type:4, Pair:5, List:6, CommutedFunc:7, Train:8, BasicFunc:9,
int:128, bool:128, str:129, tuple:130, list:131} # Override built-in comparison; bool and int are the same
# This function should be deterministic; and for all PolyLt(l,r)==True (l != r), PolyLt(r,l) should be False 
def PolyLt(l, r):
	ltypeweight = _Comparison[type(l)]
	rtypeweight = _Comparison[type(r)]
	if ltypeweight < rtypeweight: return True
	if ltypeweight > rtypeweight: return False
	if ltypeweight == 0: return False # Null == Null
	if ltypeweight == 1: return r.val and not l.val # only one: False < True
	if ltypeweight == 2: return l.val < r.val # follow Python's
	if ltypeweight == 3:
		if l == r: return False
		if r.den == 0 and l.den == 0: return r.num < l.num # NaN < Infinity
		if l.den == 0 and l.num == 0: return True # NaN < any
		if r.den == 0 and r.num == 0: return False
		return l.num * r.den < l.den * r.num
	if ltypeweight == 4: return PolyLt(l.val, r.val)
	if ltypeweight == 5:
		if l.former == r.former: return PolyLt(l.latter, r.latter)
		return PolyLt(l.former, r.former)
	if ltypeweight == 6: return PolyLt(l.val, r.val)
	if ltypeweight == 7:
		if l.index == r.index: return PolyLt(l.basis, r.basis)
		return l.index < r.index
	if ltypeweight == 8:
		if l.top == r.top: return PolyLt(l.bases, r.bases)
		return PolyLt(l.top, r.top)
	if ltypeweight == 9: return PolyLt(l.overloads, r.overloads)

	if ltypeweight == 128: return l < r
	if ltypeweight == 129: return l < r
	if ltypeweight == 130: return PolyLt(list(l), list(r))
	if ltypeweight == 131:
		for i in range(len(l)):
			if i >= len(r): return True
			if l[i] != r[i]: return PolyLt(l[i], r[i])
		return False

def isIdentifier(s, checkNumber=True):
	if not s: return False
	if checkNumber and s[0] in "1234567890": return False
	for i in s:
		if i not in "_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" and ord(i) <= 128:
			return False
	return True
def isBangRepetition(s, checkEven=False): return s.count("!") == len(s) and (not checkEven or len(s) % 2 == 0)
def tokenize(src,filename=""):
	# remove comments
	depthString = 0
	clsrc = []
	i = 0
	while i < len(src):
		if src[i] == "`": depthString += 1
		if src[i] == "'":
			if depthString == 0:
				raise PolyError("SyntaxError| Missing starting quotes.",[((filename,i) if filename else i)])
			depthString -= 1
		if depthString == 0:
			ctar = None
			if src[i:i+3]=="$$$":
				ctar="$"
				i += 3
			elif src[i:i+2]=="$$":
				ctar="\n"
				i += 2
			if ctar:
				escaped = False
				while i < len(src) and src[i] != ctar and not escaped:
					if escaped: escaped = False
					elif src[i] == "\\":
						escaped = True
					i += 1
				clsrc.append(("\n",(filename,i) if filename else i))
				i += 1
				continue
		clsrc.append((src[i],(filename,i) if filename else i))
		i += 1
	if depthString != 0: raise PolyError("SyntaxError| Unmatched opening quotes.",[((filename,i) if filename else i)])
	
	# Merge TypeStrings, normal strings, characters, numbers and identifiers
	tmpsrc1 = []
	depthString = 0
	inTypeStr = False
	statusChar = 0 # 0: not in character, 1: begin, 2: escaped
	cur, curpos = "", None
	for i, pos in clsrc:
		if depthString:
			cur += i
			if i == "`": depthString += 1
			if i == "'":
				depthString -= 1
				if depthString == 0:
					tmpsrc1.append((cur,curpos))
					cur = ""
		elif inTypeStr:
			cur += i
			if i == "$" and cur[-2] != "\\":
				inTypeStr = False
				tmpsrc1.append((cur,curpos))
				cur = ""
		elif statusChar == 1:
			if i in "\n\r": continue
			cur += i
			if i == '\\': statusChar = 2
			else:
				statusChar = 0
				tmpsrc1.append((cur,curpos))
				cur = ""
		elif statusChar == 2:
			if i in " \n\r": continue
			cur += i
			if i not in "0123456789":
				if len(cur) > 3 and i != ";": raise PolyError("SyntaxError| Expected ; in escaped character.",[pos])
				statusChar = 0
				tmpsrc1.append((cur,curpos))
				cur = ""
		elif i == "`":
			if cur: tmpsrc1.append((cur,curpos))
			cur = "`"
			curpos = pos
			depthString = 1
		# elif i == "'": impossible
		elif i == "$":
			if cur: tmpsrc1.append((cur,curpos))
			inTypeStr = True
			cur = "$"
			curpos = pos
		elif i == '"': # characters
			if cur: tmpsrc1.append((cur,curpos))
			statusChar = 1
			cur = i
			curpos = pos
		# numbers and identifiers
		elif i in "0123456789":
			if cur and not isIdentifier(cur, checkNumber=False):
				tmpsrc1.append((cur,curpos))
				cur = ""
				curpos = pos
			if not cur: curpos = pos
			cur += i
		elif i in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_" or ord(i) > 127:
			if cur and not isIdentifier(cur):
				tmpsrc1.append((cur,curpos))
				cur = ""
				curpos = pos
			if not cur: curpos = pos
			cur += i
		else:
			if cur:
				tmpsrc1.append((cur,curpos))
				cur = ""
			if i in " \n\r\t": continue
			tmpsrc1.append((i,pos))
	if cur: tmpsrc1.append((cur,curpos))
	if inTypeStr: raise PolyError("SyntaxError| Unclosed TypeString.",[curpos])
	if statusChar: raise PolyError("SyntaxError| Incomplete character.",[curpos])

	# Merge \x, x! and x. (if possible)
	tmpsrc2 = []
	lastBackslashPos = None
	for i, pos in tmpsrc1:
		if lastBackslashPos is not None:
			# possible is \+int, \+TypeString, \; | ! handled differently
			if i.isnumeric() or (i[0] == "$" and i[-1] == "$") or i == ".":
				tmpsrc2.append(("\\"+i,lastBackslashPos))
				lastBackslashPos = None
			elif i in "!;": 
				tmpsrc2.append(("\\"+i,lastBackslashPos))
				lastBackslashPos = None
			else:
				tmpsrc2.append(("\\",lastBackslashPos))
				tmpsrc2.append((i,pos))
				lastBackslashPos = None
		elif i == "\\": lastBackslashPos = pos
		elif i == ".":
			if not tmpsrc2: raise PolyError("SyntaxError| Expected token before .",[pos])
			lasttoken, lastpos = tmpsrc2.pop()
			tmpsrc2.append((lasttoken+".",lastpos))
		elif i == "!":
			if tmpsrc2: lasttoken, lastpos = tmpsrc2[-1]
			else:
				tmpsrc2.append((i,pos))
				continue
			if lasttoken[0] == "\\": # rank-lifted broadcast
				flag = True
				for j in lasttoken[1:]:
					if j != "!":
						flag = False
						break
				if flag: tmpsrc2[-1] = (lasttoken+i,lastpos)
				else: tmpsrc2.append((i,pos))
			elif lasttoken == "!": # commute
				tmpsrc2[-1] = (lasttoken+i,lastpos)
				if len(tmpsrc2) == 1: raise PolyError("SyntaxError| !! at the beginning of the code",[pos])
				if isBangRepetition(tmpsrc2[-2][0], checkEven=True):
					tmpsrc2.pop()
					tmpsrc2[-1] = (tmpsrc2[-1][0]+"!!",tmpsrc2[-1][1])
			else: tmpsrc2.append((i,pos))
		else: tmpsrc2.append((i,pos))
	if lastBackslashPos is not None: tmpsrc2.append(("\\",lastBackslashPos))

	return tmpsrc2

# Tool for file path.
def normalizePath(p, WorkingAddress=""):
	p = p.replace("\\","/")
	if not (p.startswith("/") or (len(p) > 1 and p[1] == ":" and p[2] == "/")):
		p = WorkingAddress + p
	parts = p.split("/")
	stack = []
	for part in parts:
		if part == "..":
			if stack and stack[-1] != "..": stack.pop()
			else: stack.append("..")
		elif part and part != ".":
			stack.append(part)
	if not stack: return "."
	return "/".join(stack)

def prefixtoks(tokens, prefix=""): return [(prefix+i if isIdentifier(i) else i, pos) for i, pos in tokens]
def preprocess(tokens, importer, filename="", prefix="", macros={}, returnWithNewMacros=False):
	parentdirectory = normalizePath(filename+"/../")+"/"
	res = []
	ifstack = [1] # 0 - condition not met, 1 - executing, 2 - condition already met
	for i, pos in tokens:
		if i.startswith("\\$") and i.endswith("$"):
			content = i[2:-1]
			if "+" in content: # include
				if ifstack[-1] == 1:
					filename2, prefix2 = content.rsplit("+",maxsplit=1)
					filename2 = normalizePath(filename2, parentdirectory)
					src2 = importer(filename2)
					tokens2 = tokenize(src2, filename2)
					preprocessed2, macros = preprocess(tokens2, importer, filename2, prefix2, macros, returnWithNewMacros=True)
					res += preprocessed2
			elif "#" in content: # define
				if ifstack[-1] == 1:
					name, value = content.rsplit("#",maxsplit=1)
					macros[name] = value
			elif content.endswith("*"): # undef
				if ifstack[-1] == 1:
					name = content[:-1]
					try: del macros[name]
					except KeyError: pass
			elif content.endswith(".!"): #elifdef string
				if ifstack[-1] == 0:
					if content[:-2] in macros: ifstack[-1] = 1
				else: ifstack[-1] = 2
			elif content.endswith(".?"): #elifndef string
				if ifstack[-1] == 0:
					if content[:-2] not in macros: ifstack[-1] = 1
				else: ifstack[-1] = 2
			elif content.endswith("!"): #ifdef string
				if ifstack[-1] == 1:
					if content[:-1] in macros: ifstack.append(1)
					else: ifstack.append(0)
				else: ifstack.append(2)
			elif content.endswith("?"): #ifndef string
				if ifstack[-1] == 1:
					if content[:-1] not in macros: ifstack.append(1)
					else: ifstack.append(0)
				else: ifstack.append(2)
			elif content == ".": #else
				if ifstack[-1] != 2:
					ifstack[-1] += 1
			elif content == "@": #endif
				ifstack.pop()
				if not ifstack: raise PolyError("SyntaxError| Extra \\$@$.",[pos])
			else: raise PolyError("SyntaxError| Unidentified preprocessor command.",[pos])
		elif i in macros:
			if not macros[i]: continue
			srcstr = macros[i].replace("\\$","$")
			tokens2 = tokenize(srcstr, filename)
			for j, pos2 in tokens2: res.append((j,pos2))
		else: 
			if ifstack[-1] == 1: res.append((i,pos))
	if returnWithNewMacros: return prefixtoks(res,prefix), macros
	return prefixtoks(res,prefix)

class AST:
	const = 1
	iden = 2
	apply = 3
	block = 4
	listc = 5
	func = 6
	train = 7
	cpas = 9 # Compound assignment
	comm = 10 # Commute
	diter = 11 # dIterator
	tupl = -1
	noun = -2
	verb = -3
	dflt = 0 # other syntactic constructs
	paply = 13 # Partial application

def parse(tokens):
	def isVerbTok(name):
		if name.endswith(".") and not (name[:-1].isdigit() or name[0] == "\\" and name[1:-1].isdigit()) and name != '".': return True
		if name in list("#%&*+,-/:<=?@^|~"): return True
		return False
	def classify(tok): # Classify tokens into nouns, verbs, and others & deals with (), [], {} and adverbs.
		res = []
		i = 0
		while i < len(tok):
			t, pos = tok[i]
			if t in ["(","[","{"]:
				brackets = [t]; j = i + 1
				pos2 = pos
				while brackets and j < len(tok):
					t2, pos2 = tok[j]
					if t2 in [")","]","}"]:
						if {"(":")","[":"]","{":"}"}[brackets.pop()] != t2: raise PolyError("SyntaxError| Mismatched brackets", [pos2])
					elif t2 in ["(","[","{"]:
						brackets.append(t2)
					j += 1
				j -= 1
				if brackets: raise PolyError("SyntaxError| Mismatched brackets", [pos2])
				parsed = classify(tok[i+1:j])
				if t == "(": res.append((AST.noun, pos, (AST.tupl, pos, parsed)))
				elif t == "[": res.append((AST.noun, pos, (AST.listc, pos, parsed)))
				elif t == "{":
					if not parsed or parsed[0][0] != AST.verb:
						res.append((AST.noun, pos, (AST.block, pos, parsed)))
					else: res.append((AST.verb, pos, (AST.train, pos, parsed)))
				i = j
			elif t in [")","]","}"]: raise PolyError("SyntaxError| Mismatched brackets", [pos])
			elif t[0] == "\\" and isBangRepetition(t[1:]): res.append((AST.dflt, pos, t))
			elif t in [">",";"]: res.append((AST.dflt, pos, t))
			elif isBangRepetition(t): res.append((AST.dflt, pos, t))
			elif isVerbTok(t): res.append((AST.verb, pos, t))
			else: res.append((AST.noun, pos, t))
			i += 1
		
		# Suffix adverbs scan (`!`,`!!...`)
		tmp = []
		for kind, pos, tok in res:
			if kind == AST.dflt:
				if tok == "!":
					if not tmp: raise PolyError("SyntaxError| Invalid suffix adverb", [pos])
					lastkind = tmp[-1][0]
					if lastkind == AST.noun: tmp[-1] = (AST.verb, tmp[-1][1], tmp[-1][2])
					elif lastkind == AST.verb: tmp[-1] = (AST.noun, tmp[-1][1], tmp[-1][2])
					else: raise PolyError("SyntaxError| Invalid suffix adverb", [pos])
				elif isBangRepetition(tok):
					if not tmp: raise PolyError("SyntaxError| Invalid suffix adverb", [pos])
					tmp[-1] = (tmp[-1][0], pos, (AST.comm, pos, tmp[-1], len(tok) // 2))
				else: tmp.append((kind, pos, tok))
			else: tmp.append((kind, pos, tok))
		# Prefix adverbs scan (`#`,`\!!...!`)
		res = []
		for kind, pos, tok in reversed(tmp):
			if kind == AST.dflt and tok[0] == "\\":
				if not res: raise PolyError("SyntaxError| Invalid prefix adverb", [pos])
				res[-1] = (res[-1][0], pos, (AST.diter, pos, res[-1], len(tok) - 1))
			elif kind == AST.verb and isinstance(tok, str) and tok == "#":
				if not res: res.append((kind, pos, tok))
				elif res[-1][0] != AST.verb: res.append((kind, pos, tok))
				else: res[-1] = (AST.verb, pos, (AST.cpas, pos, res[-1]))
			else: res.append((kind, pos, tok))

		return res[::-1]
	classified = classify(tokens)
	def nest(token, autoPadLeftArg=True, parseTrain=False):
		# First scan backward and merge verb-noun pairs
		tmp = []
		semicolon = False
		for i in reversed(token):
			kind, pos, tok = i
			if isinstance(tok, tuple):
				kind2, pos2, *children = tok
				if kind2 == AST.train:
					children[0] = nest(children[0], autoPadLeftArg=False, parseTrain=True)
				else:
					if isinstance(children[0], tuple): children[0] = nest([children[0]], autoPadLeftArg=False)[0]
					elif isinstance(children[0], list): children[0] = nest(children[0])
				tok = kind2, pos2, *children
			elif isinstance(tok, str):
				if isIdentifier(tok) or isVerbTok(tok): tok = (AST.iden, pos, tok)
				elif tok in list(">;"): tok = (AST.dflt, pos, tok)
				else: tok = (AST.const, pos, tok)
			if kind == AST.verb and not semicolon and tmp and tmp[-1][0] == AST.noun:
				tmp[-1] = (AST.verb, pos, (AST.paply, pos, tok, tmp[-1]))
				semicolon = False
			else:
				semicolon = kind == AST.dflt and isinstance(tok, tuple) and tok[2] == ";"
				if not semicolon: tmp.append((kind, pos, tok))

		if parseTrain:
			res = []
			for kind, pos, tok in reversed(tmp):
				if kind == AST.dflt:
					if tok[2] == ">": raise PolyError("SyntaxError| Expected verb or phrase inside train", [pos])
				elif kind == AST.noun: raise PolyError("SyntaxError| Expected verb or phrase inside train", [pos])
				else:
					if tok[0] == AST.paply:
						_, pos2, func, *args = tok
						for i in range(len(args)):
							if isinstance(args[i], tuple) and len(args[i]) == 3 and args[i][0] == AST.noun:
								args[i] = args[i][2]
						res.append((AST.func, pos2, [(AST.iden, pos2, "")], (AST.apply, pos2, func, (AST.iden, pos2, ""), *args)))
					else: res.append(tok)
			return res
		# Then scan forward for the left operand
		res = []
		isLambdaExpr = False
		for kind, pos, tok in reversed(tmp):
			if kind == AST.noun:
				if isinstance(tok, tuple) and len(tok) == 3 and tok[0] == AST.tupl:
					content = tok[2]
					if len(content) != 1: raise PolyError("SyntaxError| Multiple objects in parentheses", [pos])
					res.extend(content)
				else: res.append(tok)
			elif kind == AST.verb and autoPadLeftArg:
				if isinstance(tok, tuple) and tok[0] == AST.paply:
					_, pos2, verb, obj = tok
					if isinstance(verb, str):
						if isIdentifier(verb) or isVerbTok(verb): verb = (AST.iden, pos2, verb)
						else: verb = (AST.const, pos2, verb)
					if isinstance(obj, tuple) and len(obj) == 3 and obj[0] in (AST.noun, AST.verb, AST.dflt):
						obj_kind, obj_pos, obj_tok = obj
						if isinstance(obj_tok, str):
							if isIdentifier(obj_tok) or isVerbTok(obj_tok): obj_tok = (AST.iden, obj_pos, obj_tok)
							else: obj_tok = (AST.const, obj_pos, obj_tok)
						obj = obj_tok
					if not res or (res[-1][0] == AST.dflt and res[-1][2] == ">"):
						res.append((AST.iden, None, ""))
						res.append((AST.dflt, None, ">"))
						res.append((AST.iden, None, ""))
						isLambdaExpr = True
					if isinstance(obj, tuple) and obj[0] == AST.tupl:
						res[-1] = (AST.apply, pos2, verb, res[-1], *obj[2])
					else:  res[-1] = (AST.apply, pos2, verb, res[-1], obj)
				else:
					if not res or (res[-1][0] == AST.dflt and res[-1][2] == ">"):
						res.append((AST.iden, None, ""))
						res.append((AST.dflt, None, ">"))
						res.append((AST.iden, None, ""))
						isLambdaExpr = True
					res[-1] = (AST.apply, pos, tok, res[-1])
			elif kind == AST.dflt and tok[2] == ">":
				if parseTrain: raise PolyError("SyntaxError| Invalid syntax inside train", [pos])
				isLambdaExpr = True
				res.append(tok)
			else: res.append(tok)
		if isLambdaExpr:
			segments = [[]]
			greaterpos = []
			for i in res:
				if i[0] == AST.dflt and i[2] == ">":
					segments.append([]); greaterpos.append(i[1])
				else: segments[-1].append(i)
			if len(segments[-1]) == 0: raise PolyError("SyntaxError| Invalid syntax", [greaterpos[-1]])
			res2 = segments[-1]
			j = len(greaterpos) - 1
			for i in segments[-2::-1]:
				res2 = (AST.func, greaterpos[j], i, res2)
				j -= 1
			return [res2]
		return res
	res = nest(classified)
	return res

def _isNumeric(s):
	if not s: return False
	return s[s[0] == "\\" : -1 if s[-1] == "." else None].isdigit()

def _traverseAssignment(ast, define=False):
	kind, pos, *args = ast
	if kind == AST.const:
		if args[0] != "\\;": raise PolyError("SyntaxError| Cannot assign to constant", [pos])
		return [(Inst.DROP,pos,args[0])]
	if kind == AST.iden: return [(Inst.DEFINE if define else Inst.SET,pos,args[0])]
	if kind == AST.apply:
		if not isinstance(args[0], tuple) or args[0][2] != ",": raise PolyError("SyntaxError| Cannot assign to expression", [pos])
		arity = len(args) - 1
		if arity > 2: raise PolyError("SyntaxError| Cannot assign to expression", [pos])
		if arity == 1: return [(Inst.EXPANDLIST,pos,1)] + _traverseAssignment(args[1], define)
		if arity == 2: return [(Inst.EXPANDPAIR,pos)] + _traverseAssignment(args[2], define) + _traverseAssignment(args[1], define)
	elif kind == AST.comm: return _traverseAssignment(args[0], define)
	elif kind == AST.diter: return _traverseAssignment(args[0], not define)
	elif kind == AST.listc:
		prefn, postfn, metsplitter = 0, 0, False
		res = []
		for i in reversed(args[0]):
			if i[0] == AST.comm or (i[0] == AST.diter and i[2][0] == AST.comm):
				if metsplitter: raise PolyError("SyntaxError| Too many expansions in assignment", [pos])
				metsplitter = True
			elif metsplitter: prefn += 1
			else: postfn += 1
			res.extend(_traverseAssignment(i, define))
		if metsplitter: return [(Inst.EXPANDLIST,pos,prefn,postfn)] + res
		else: return [(Inst.EXPANDLIST,pos,postfn)] + res
	else: raise PolyError("SyntaxError| Cannot assign to expression", [pos])
def compile(ast):
	kind, pos, *args = ast
	if kind == AST.const:
		val = args[0]
		if val == "\\;": return [(Inst.PUSH,pos,NULL)]
		if _isNumeric(val): # number (Expr)
			negative = val[0] == "\\"
			if negative: val = val[1:]
			scientific = val[-1] == "."
			if scientific: val = val[:-1]
			body = int(val)
			if scientific: body = 10 ** body
			if negative: resconst = Expr(1,body) if scientific else Expr(-body)
			else: resconst = Expr(body)
			return [(Inst.PUSH,pos,resconst)]
		if val[0] == "`": return [(Inst.PUSH,pos,List(val[1:-1]))] # string (List)
		if val[0] == '"': # Char
			if val[1] == "\\":
				val = val[2:]
				if val[:-1].isdigit(): return [(Inst.PUSH,pos,Char(chr(int(val[:-1]))))]
				return [(Inst.PUSH,pos,Char({"n":"\n","t":"\t","r":"\r","b":"\b","p":"`","q":"'",";":"\0"}[val]))]
			return [(Inst.PUSH,pos,Char(val[1]))]
		if val[0] == "$": return [(Inst.PUSH,pos,Type(val))] # TypeString (Type)
	elif kind == AST.iden:
		if args[0] and args[0][0] == "\\" and args[0][-1] == ".":
			return [(Inst.RECUR,pos,len(args[0])-1)]
		return [(Inst.GET,pos,args[0])]
	elif kind == AST.tupl:
		if len(args[0]) != 1: raise PolyError("SyntaxError| Multiple objects in parentheses", [args[0]]) # unreachable
		return compile(args[0][0])
	elif kind == AST.apply:
		function, *args = args
		arity = len(args)
		if isinstance(function, tuple) and function[0] == AST.iden:
			name = function[2]
			if name == "#" and arity == 1:
				if args[0][0] != AST.iden: raise PolyError("SyntaxError| Cannot perform closure on non-identifier", [pos])
				return [(Inst.CLOSURE,pos,args[0][2])]
			elif name == "#" and arity == 2: return compile(args[0]) + [(Inst.DUP,pos,1)] + _traverseAssignment(args[1])
			elif name == "?":
				if arity == 1: return compile(args[0]) + [(Inst.DROP,pos,1),(Inst.PUSH,pos,CONT)]
				blocks = [compile(i) for i in args]
				if arity % 2 == 0: blocks.append([(Inst.PUSH,pos,CONT)])
				suffixsum = [-1]
				for i in reversed(blocks): suffixsum.append(suffixsum[-1]+len(i)+1)
				suffixsum.pop()
				res = []
				for i in range(0, arity//2*2, 2):
					res.extend(blocks[i])
					res.append((Inst.JF,pos,len(blocks[i+1])+1))
					res.extend(blocks[i+1])
					suffixsum.pop()
					res.append((Inst.JMP,pos,suffixsum.pop()))
				res.extend(blocks[-1])
				return res
			elif name == "@":
				if arity == 1: return compile(args[0]) + [(Inst.RETURN,pos)]
				if arity == 2:
					sgmt1 = compile(args[0])
					sgmt2 = compile(args[1])
					return [(Inst.PUSHMARK,pos)] + sgmt1 + [(Inst.JF,pos,len(sgmt2)+1)] + sgmt2 + [
						(Inst.JMP,pos,-len(sgmt2)-len(sgmt1)-2),(Inst.CONSLIST,pos)]
			elif name == ":":
				if arity == 1: return compile(args[0]) + [(Inst.RAISE,pos)]
				if arity == 2:
					trybody = compile(args[0])
					exceptbody = compile(args[1])
					return [(Inst.TRY,pos,len(trybody)+1)] + trybody + [(Inst.EXCEPT,pos,len(exceptbody))] + exceptbody
		res = []
		for i in args: res.extend(compile(i))
		if isinstance(function, tuple) and function[0] == AST.cpas:
			res.extend(compile(function[2]))
			res.append((Inst.APPLY,pos,arity))
			res.append((Inst.DUP,pos,1))
			res.extend(_traverseAssignment(args[0]))
			return res
		res.extend(compile(function))
		res.append((Inst.APPLY,pos,arity))
		return res
	elif kind == AST.block:
		if len(args[0]) == 0: return [(Inst.PUSH,pos,NULL)]
		res = [(Inst.ENTERSCOPE,pos)]
		for i in args[0]:
			res.extend(compile(i))
			res.append((Inst.DROP,pos,1))
		res[-1] = (Inst.EXITSCOPE,pos)
		return res
	elif kind == AST.listc:
		res = [(Inst.PUSHMARK,pos)]
		const, optimize = [], True
		for i in args[0]:
			subcode = compile(i)
			res.extend(subcode)
			if optimize:
				if len(subcode) == 1 and subcode[0][0] == Inst.PUSH: const.append(subcode[0][2])
				else: optimize = False
		if optimize: return [(Inst.PUSH,pos,List(const))]
		res.append((Inst.CONSLIST,pos))
		return res
	elif kind == AST.func:
		args, body = args
		arg_init, arg_types = [], []
		for i in args:
			if i[0] == AST.iden:
				arg_init.append((Inst.DEFINE,i[1],i[2]))
				arg_types.append(Type("$*$"))
			elif i[0] == AST.const:
				if i[2] == "\\;":
					arg_init.append((Inst.DROP,pos,1))
					arg_types.append(Type("$*$"))
					continue
				if i[2][0] != "$": raise PolyError("SyntaxError| Cannot use constant in argument of function", [i[1]])
				if not arg_types: raise PolyError("SyntaxError| Typing should be written after an identifier", [i[1]])
				arg_types[-1] = Type(i[2])
			else: raise PolyError("SyntaxError| Cannot use non-identifier or constant in argument of function", [i[1]])
		if not arg_init: raise PolyError("SyntaxError| Functions must have at least one argument", [pos])
		if not isinstance(body, list): body = [body]
		body = [(Inst.ENTERSCOPE,pos)] + arg_init[::-1] + compile((AST.block,pos,body))[1:] # remove ENTERSCOPE
		closures = []
		for i,j in enumerate(body):
			if j[0] == Inst.CLOSURE: closures.append(i)
		if closures: return [(Inst.LOADLAMBDA,pos,arg_types,body,closures)]
		return [(Inst.PUSH,pos,BasicFunc([(arg_types,body)]))] # Optimization for non-closure function
	elif kind == AST.comm: return compile(args[0]) + [(Inst.COMMUTE,pos,args[1])]
	elif kind == AST.train:
		res = []
		for i in args[0]: res.extend(compile(i))
		res.append((Inst.CONSTRAIN,pos,len(args[0])))
		return res
	elif kind == AST.diter:
		return compile(args[0]) + [(Inst.CONSITER,pos,args[1])]
	raise PolyError("SyntaxError| Unknown syntax", [pos])

stdlib = {}
def _register(name,types):
	args = [Type("$"+_+"$") for _ in types]
	def wrapper(f):
		j = stdlib.setdefault(name,BasicFunc(name=name))
		j.config(args,f)
	return wrapper

def vmcall(func, *args): # Usage: res = yield vmcall("+", Expr(1), Expr(2)) -> res = Expr(3)
	res = []
	for i in args: res.append((Inst.GET if isinstance(i,str) else Inst.PUSH,"<native>",i))
	res.append((Inst.GET if isinstance(func,str) else Inst.PUSH,"<native>",func))
	res.append((Inst.APPLY,"<native>",len(args)))
	return res
_consconsstruct = lambda x: BasicFunc([([Type("$*$")],[(Inst.CONSSTRUCT,"<fallback>",x)])])


# Utils
def _kmpfind(lst, sub, overlap=True): # Knuth-Morris-Pratt algorithm
	n, m = len(lst), len(sub)
	if m == 0: return []
	if m > n: return []
	pi = [0] * m
	j = 0
	for i in range(1, m):
		while j > 0 and sub[i] != sub[j]: j = pi[j - 1]
		if sub[i] == sub[j]: j += 1
		pi[i] = j
	res = []
	j = 0
	for i in range(n):
		while j > 0 and lst[i] != sub[j]: j = pi[j - 1]
		if lst[i] == sub[j]: j += 1
		if j == m:
			res.append(i - m + 1)
			if overlap: j = pi[m - 1]
			else: j = 0
	return res
def _reshape(lst, l):
	if l <= 0: return lst[:-l]
	if not lst: raise PolyError("ValueError| Cannot reshape empty list", [])
	return (lst*(l//len(lst)+1))[:l]

def _float2frac(x, max_denominator = 1000000):
	sign = 1
	if isinf(x): return Expr(1, 0)
	if isnan(x): return Expr(0, 0)
	if x < 0: sign = -1; x = -x
	h_minus2, k_minus2 = 0, 1
	h_minus1, k_minus1 = 1, 0
	last_h, last_k = 0, 1
	while True:
		a = floor(x)
		h = a * h_minus1 + h_minus2
		k = a * k_minus1 + k_minus2
		if k > max_denominator:
			t = (max_denominator - k_minus2) // k_minus1
			if t == 0: return Expr(sign * last_h, last_k)
			cand1_h, cand1_k = h_minus1, k_minus1
			cand2_h = t * h_minus1 + h_minus2
			cand2_k = t * k_minus1 + k_minus2
			err1 = abs(cand1_h / cand1_k - x)
			err2 = abs(cand2_h / cand2_k - x)
			if err2 <= err1:
				return Expr(sign * cand2_h, cand2_k)
			else:
				return Expr(sign * cand1_h, cand1_k)
		last_h, last_k = h, k
		if x == a: return Expr(sign * h, k)
		x = 1.0 / (x - a)
		h_minus2, k_minus2 = h_minus1, k_minus1
		h_minus1, k_minus1 = h, k
def Polyify(obj):
	if type(obj) == bool: return Bool(obj)
	if type(obj) == int: return Expr(obj)
	if type(obj) == float: return _float2frac(obj)
	if type(obj) == str: return List(obj)
	if type(obj) == list: return List([Polyify(i) for i in obj])
	if obj is None: return NULL
	if type(obj) == dict: return Pair(List(obj.keys()),List(obj.values()))
def dePolyify(obj):
	if type(obj) == Bool: return obj.val
	if type(obj) == Expr: return obj.num / obj.den
	if type(obj) == List:
		try: return str(obj.val)
		except TypeError: return [dePolyify(i) for i in obj]
	if type(obj) == NULL: return None
	if type(obj) == Pair:
		if type(obj.former) != List or type(obj.latter) != List: raise PolyError("ValueError| Pair must have List keys and List values", [])
		try: return {dePolyify(i):dePolyify(j) for i,j in zip(obj.former.val, obj.latter.val)}
		except TypeError: raise PolyError("ValueError| Unhashable key in dict")
	raise PolyError("ValueError| Unsupported type", [])



# Symbols

@_register("%",['[,]']) # Transpose (List<Pair> -> Pair<List,List>)
def _(x):
	former = []
	latter = []
	for i in x.val:
		former.append(i.former)
		latter.append(i.latter)
	return Pair(List(former),List(latter))
@_register("%",['[],[]']) # Transpose (Pair<List,List> -> List<Pair>, trims longer list)
def _(x): return List([Pair(i,j) for i,j in zip(x.former.val, x.latter.val)])
@_register("%",['[[]]']) # Transpose (List<List>, simulates gravity)
def _(x):
	res = []
	for i in x.val:
		for j,v in enumerate(i.val):
			if len(res) <= j: res.append([])
			res[j].append(v)
	return List([List(i) for i in res])
_register("%",['+','+'])(Expr.__mod__) # Modulus
@_register("%",['[]','*']) # Where
def _(l,o):
	res = []
	for i,j in enumerate(l.val):
		if j == o: res.append(Expr(i))
	return List(res)


_register("&", ['*'])(lambda obj:Type(_jtypeof(obj), analyze=False))  # Type of
_register("&", ['=','='])(lambda x,y:x and y)  # AND
_register("&", ['+','+'])(lambda x,y: Expr(gcd(x.num,y.num), lcm(x.den,y.den)))  # GCD
@_register("&", ['[]','[]'])  # Set intersection
def _(x,y):
	res = []
	yv = y.val.copy()
	for i in x.val:
		if i in yv:
			res.append(i)
			yv.remove(i)
	return List(res)
@_register("&", ['[]','+'])  # Rotation
def _(x,r):
	if r.den != 1: raise PolyError("ValueError| Rotation value must be an integer", [])
	lx = len(x.val)
	if lx == 0: return x
	return List(x.val[r.num%lx:]+x.val[:r.num%lx])
_register("&", ['*','/'])(lambda o,t: Bool(t.match(o)))  # Check if is instance
@_register("&", ['[]','[]',';'])  # Split by delimiter
def _(l,d,null):
	lv, dv = l.val, d.val
	ld = len(dv)
	indices = _kmpfind(lv, dv, overlap=False)
	res = []
	cur = 0
	for i in indices:
		res.append(List(lv[cur:i]))
		cur = i + ld
	res.append(List(lv[cur:]))
	return List(res)
@_register("&", ['[]','[]','+'])  # Split by delimiter with maxsplit
def _(l,d,maxsplit):
	if maxsplit.den != 1: raise PolyError("ValueError| Maxsplit must be an integer", [])
	lv, dv = l.val, d.val
	ld = len(dv)
	indices = _kmpfind(lv, dv, overlap=False)
	res = []
	cur = 0
	for i in indices[:maxsplit.num]:
		res.append(List(lv[cur:i]))
		cur = i + ld
	res.append(List(lv[cur:]))
	return List(res)


_register("*", ['+'])(lambda x:-x if x.num < 0 else x)  # Absolute value
_register("*", ['+','+'])(Expr.__mul__)  # Multiplication
@_register("*", ['[]','+'])  # List repetition
def _(l,n):
	lv = l.val; ll = len(lv)
	if n.den == 0 or ll % n.den != 0: raise PolyError("ValueError| List length must be divisible by repetition factor", [])
	tarlen = ll*n.num // n.den
	return List(_reshape(lv, tarlen))
@_register("*", ['[]','[]'])  # Indexes of substrings
def _(l,s): return List([Expr(i) for i in _kmpfind(l.val, s.val, overlap=True)])
@_register("*", ['[]','[]','[]'])  # Replace substrings
def _(l,s,r):
	lv, sv, rv = l.val, s.val, r.val
	ld = len(sv)
	indices = _kmpfind(lv, sv, overlap=False)
	res = []
	cur = 0
	for i in indices:
		res.extend(lv[cur:i])
		res.extend(rv)
		cur = i + ld
	res.extend(lv[cur:])
	return List(res)
@_register("*", ['*','>','[]'])  # Iterate over a list
def _(o,f,l):
	for i in l.val:
		o = yield vmcall(f, o, i)
	return o
@_register("*", ['[]','[]','[]','+'])  # Replace substrings with maxreplace
def _(l,s,r,maxreplace):
	if maxreplace.den != 1: raise PolyError("ValueError| Maxreplace must be an integer", [])
	lv, sv, rv = l.val, s.val, r.val
	ld = len(sv)
	indices = _kmpfind(lv, sv, overlap=False)
	res = []
	cur = 0
	for i in indices[:maxreplace.num]:
		res.extend(lv[cur:i])
		res.extend(rv)
		cur = i + ld
	res.extend(lv[cur:])
	return List(res)

@_register("+", ['+'])  # Floor
def _(x): return x if x.den == 0 else Expr(x.num // x.den)
@_register("+", ['[]'])  # Sort index
def _(x):
	arr = x.val
	def merge_sort(l):
		ll = len(l)
		if ll <= 1: return l
		mid = ll // 2; ll -= mid
		left = yield from merge_sort(l[:mid])
		right = yield from merge_sort(l[mid:])
		res = []; i = j = 0
		while i < mid and j < ll:
			if left[i][0] == right[j][0]:
				res.append(left[i]); res.append(right[j]); i += 1; j += 1; continue
			flag = yield vmcall("<", left[i][0], right[j][0])
			if flag: res.append(left[i]); i += 1
			else: res.append(right[j]); j += 1
		res.extend(left[i:]); res.extend(right[j:])
		return res
	sortedl = yield from merge_sort([(j,i) for i,j in enumerate(arr)])
	rank = [0] * len(arr)
	current_rank = Expr(0)
	for pos, (val, idx) in enumerate(sortedl):
		if pos == 0 or val != sortedl[pos-1][0]:
			current_rank = Expr(pos)
		rank[idx] = current_rank
	return List(rank)


@_register("+", ['+,+'])  # Random integer between
def _(x):
	x, y = x.former, x.latter
	if x.den == 0 or y.den == 0: return Expr(0, 0) # NaN
	lower = -((-x.num)//x.den)
	upper = -((-y.num)//y.den)
	if lower >= upper: return Expr(0, 0) # NaN
	return Expr(randint(lower, upper-1))
_register("+", ['+','+'])(Expr.__add__)  # Addition
_register("+", ['[]','[]'])(List.__add__)  # Concatenation
@_register("+", ['[]','+|;'])  # Random sample/shuffle
def _(x,k):
	if isinstance(k, Null): k = Expr(len(x.val))
	if k.den != 1: raise PolyError("ValueError| Sample size must be an integer", [])
	if k.num < 0 or k.num > len(x.val): raise PolyError("ValueError| Sample larger than population or is negative", [])
	return List(sample(x.val, k.num))
_register("+", ['>','>'])(lambda x,y:x+y)  # Merge


_register(",", ['*'])(lambda x: List([x]))
_register(",", ['*','*'])([(Inst.CONSPAIR,"<native>")])


@_register("-", ['[]'])  # Remove duplicates
def _(x):
	seen = []
	res = []
	for i in x.val:
		if i not in seen:
			seen.append(i)
			res.append(i)
	return List(res)
_register("-", ['+'])(Expr.__neg__)  # Negate
_register("-", ['='])(Bool.__neg__)  # NOT
_register("-", ['+','+'])(Expr.__sub__)  # Subtraction
@_register("-", ['[]','[]'])  # Set difference
def _(x,y):
	res = []
	yv = y.val.copy()
	for i in x.val:
		if i not in yv: res.append(i)
		else: yv.remove(i)
	return List(res)
@_register("-", ['[]','+'])  # Split into heads and tails
def _(x,pos):
	if pos.den != 1: raise PolyError("ValueError| Position must be an integer", [])
	return Pair(List(x.val[:pos.num]), List(x.val[pos.num:]))


_register("/", ['+'])(lambda x:Expr(x.den, x.num))  # Reciprocal
_register("/", ['[]'])(lambda x:List(x.val[::-1]))  # Reverse
_register("/", [','])(lambda x:Pair(x.latter, x.former))  # Swap
_register("/", ['+','+'])(Expr.__truediv__)  # Division
_register("/", ['[]','+|[+|=]|(+|;),(+|;)'])(List.__getitem__)  # Get Item (List)
_register("/", [',' ,'=|[+|=]'])(Pair.__getitem__)  # Get Item (Pair)
_register("/", ['[]','+|[+|=]|(+|;),(+|;)','*'])(List.setitem)  # Set Item (List)
_register("/", [',','=|[+|=]','*'])(Pair.setitem)  # Set Item (Pair)
@_register("/", ['[]|,','>','+|=|[+|=]|(+|;),(+|;)'])  # Apply on Item
def _(l,f,i):
	value = l[i]
	res = yield vmcall(f, value)
	return l.setitem(i, res)


_register("<", ['[]'])(lambda l:Expr(len(l.val)))  # Length
_register("<", [','])(lambda x:x.former)  # Former
_register("<", ['+'])(lambda x:Expr(x.num))  # Numerator
_register("<", ['"'])(lambda x:Expr(ord(x.val)))  # ASCII
@_register("<", ['*'])  # Value behind
def _(x):
	if not isinstance(x, UserDefinedTypeObject): raise PolyError("TypeError| Expected struct", [])
	return x.value
_register("<", ['*','*'])(lambda x,y:Bool(PolyLt(x,y)))  # Less-than comparison


@_register("=", ['[]'])  # Flat
def _(x):
	res = []
	for i in x.val:
		if isinstance(i, List): res.extend(i.val)
		else: res.append(i)
	return List(res)
@_register("=", ['+'])  # Range
def _(x):
	if x.den != 1: raise PolyError("ValueError| Range must be an integer", [])
	return List([Expr(i) for i in range(x.num)])
_register("=", ['*','*'])(lambda x,y:Bool(x == y))  # Equality
@_register("=", ['+','+','+'])  # Range with start-end-step
def _(s,f,t):
	if s.num == 0: raise PolyError("ValueError| Step must be non-zero", [])
	if s.den == 0: return List([])
	res = []
	if s.num < 0:
		while t.num * f.den < f.num * t.den:
			res.append(f)
			f += s
	else:
		while f.num * t.den < t.num * f.den:
			res.append(f)
			f += s
	return List(res)


@_register("^", ['[]'])  # Enumerate
def _(x):
	res = []
	for i in range(len(x.val)):
		res.append(Pair(Expr(i), x.val[i]))
	return List(res)
_register("^", ['=','='])(lambda x,y: Bool(x != y))  # XOR
@_register("^", ['[]','[]'])  # Setwise XOR
def _(x,y):
	yv = y.val.copy()
	res = []
	for i in x.val:
		if i not in yv: res.append(i)
		else: yv.remove(i)
	res.extend(yv)
	return List(res)
@_register("^", ['[]','+'])  # Reshape
def _(x,l):
	if l.den != 1: raise PolyError("ValueError| Shape must be an integer", [])
	return List(_reshape(x.val, l.num))
@_register("^", ['*','>','+'])  # Apply for n times
def _(x,f,n):
	res = x
	if n.den != 1: raise PolyError("ValueError| Number must be an integer", [])
	for i in range(n.num):
		res = yield vmcall(f, res)
	return res
@_register("^", ['[]','+','*'])  # Reshape with default value
def _(x,l,v):
	if l.den != 1: raise PolyError("ValueError| Shape must be an integer", [])
	t = l.num - len(x.val)
	if t < 0: return List(x.val[:t])
	return List(x.val + [v] * t)


_register("|", ['*'])(lambda x: Bool(bool(x)))  # Convert to Boolean
_register("|", ['=','='])(lambda x,y: x or y)  # OR
_register("|", ['+','+'])(lambda x,y: Expr(lcm(x.num,y.num),gcd(x.den,y.den)))  # LCM
@_register("|", ['[]','[]'])  # Union
def _(x,y):
	res = x.val.copy()
	res.extend([i for i in y.val if i not in x.val])
	return List(res)
@_register("|", ['[]','+'])  # Regroup
def _(x,l):
	if l.den != 1: raise PolyError("ValueError| Shape must be an integer", [])
	res = []
	for i in range(0,len(x.val),l.num):
		res.append(List(x.val[i:i+l.num]))
	return List(res)


@_register("~", ['+'])  # Char
def _(x):
	if x.den != 1: raise PolyError("ValueError| Code point must be an integer", [])
	return Char(chr(x.num))
_register("~", ['["]'])([(Inst.EVAL,"<native>")])  # Evaluate
@_register("~", ['*','>'])  # Apply until fixed-point
def _(x,f):
	last = x
	while True:
		x = yield vmcall(f, x)
		if x == last: return x
		last = x
@_register("~", ['*','>','+'])  # Apply until fixed-point with time limit
def _(x,f,n):
	last = x
	if n.den != 1: raise PolyError("ValueError| Number must be an integer", [])
	for i in range(n.num):
		x = yield vmcall(f, x)
		if x == last: return x
		last = x
	return x
@_register("~", ['*','>',';'])  # Apply until periodic
def _(x,f,null):
	hist = []
	while True:
		hist.append(x)
		x = yield vmcall(f, x)
		if x in hist: return List(hist[hist.index(x):])
@_register("~", ['*','+','>'])  # Apply until period with time limit
def _(x,n,f):
	hist = []
	if n.den != 1: raise PolyError("ValueError| Number must be an integer", [])
	for i in range(n.num):
		hist.append(x)
		x = yield vmcall(f, x)
		if x in hist: return Pair(Bool(True), List(hist[hist.index(x):]))
	return Pair(Bool(False), x)


@_register("%.", ['["]'])  # ls
def _(x):
	path = str(x)
	try:
		with os.scandir(path) as entries:
			folders = []
			files = []
			for entry in entries:
				if entry.is_dir(): folders.append(List(entry.name))
				if entry.is_file(): files.append(List(entry.name))
		return Pair(List(folders), List(files))
	except FileNotFoundError: raise PolyError("FileError| Cannot access directory", [])


_register("&.", ['*'])(lambda x: List(PolyRepr(x)))  # Repr
@_register("&.", ['[]','>'])  # Filter (function)
def _(x,f):
	res = []
	for i in x.val:
		mask = yield vmcall(f, i)
		if mask: res.append(i)
	return List(res)
@_register("&.", ['[]','[=]'])  # Filter (mask)
def _(x,y): return List([i for i,j in zip(x.val,y.val) if j])


_register("*.", ['*'])(lambda x: List(str(x)))  # Str
@_register("*.", ['[]','[+]'])  # Partition
def _(x,l):
	xv, lv = x.val, l.val
	res = []
	cur = 0
	for i in lv:
		if i.den != 1 or i.num < 0: raise PolyError("ValueError| Partition value must be a non-negative integer", [])
		res.append(List(xv[cur:cur+i.num]))
		cur += i.num
	return List(res)


@_register("+.", ['[]'])  # Run-length encoding
def _(x):
	xv = x.val
	if not xv: return Pair(List([]), List([]))
	cnt = [1]
	res = [xv[0]]
	for i in xv[1:]:
		if i == res[-1]: cnt[-1] += 1
		else:
			cnt.append(1)
			res.append(i)
	return Pair(List([Expr(i) for i in cnt]), List(res))
@_register("+.", ['+','+'])  # Encode (Base conversion)
def _(x,b):
	if x.den != 1: raise PolyError("ValueError| Cannot encode non-integer", [])
	if x.num < 0: raise PolyError("ValueError| Cannot encode negative integers (unsupported)", [])
	n = x.num
	if b.den == 0: raise PolyError("ValueError| Base cannot be infinity or NaN", [])
	p = b.num; q = b.den
	if q <= 0 or p <= q: raise PolyError("ValueError| Base must be a rational > 1", [])
	if n == 0: return List([])
	digits = []
	while n != 0:
		d = n % p
		digits.append(Expr(d))
		n = (n - d) * q // p
	digits.reverse()
	return List(digits)
@_register("+.", ['["]','["]|;']) # String encoding
def _(x,c):
	srcstr = str(x)
	coding = "UTF-8" if isinstance(c, Null) else str(c)
	try: return List([Expr(i) for i in srcstr.encode(coding)])
	except LookupError: raise PolyError("ValueError| Unknown encoding scheme", [])
	except UnicodeEncodeError: raise PolyError("ValueError| Unicode encoding error", [])
@_register("+.", ['[+]','+'])  # Decode (Base conversion)
def _(x,b):
	acc = Expr(0)
	for i in x.val: acc = acc * b + i
	return acc
@_register("+.", ['[+]','["]|;'])  # String decoding
def _(x,c):
	srcstr = b''
	for i in x.val:
		if i.den != 1: raise PolyError("ValueError| Cannot decode non-integer", [])
		srcstr += bytes([i.num])
	coding = "UTF-8" if isinstance(c, Null) else str(c)
	try: return List(srcstr.decode(coding))
	except LookupError: raise PolyError("ValueError| Unknown decoding scheme", [])
	except UnicodeDecodeError: raise PolyError("ValueError| Unicode decoding error", [])
@_register("+.", ['[]','[+]'])  # Group (Mask)
def _(x,g):
	res = []
	for i,j in zip(x.val,g.val):
		if j.den != 1 or j.num < 0: raise PolyError("ValueError| Group mask must be a non-negative integer", [])
		while len(res) <= j.num: res.append([])
		res[j.num].append(i)
	return List([List(i) for i in res])
@_register("+.", ['[]','>'])  # Group (Function)
def _(x,g):
	res = []
	for i in x.val:
		j = yield vmcall(g, i)
		if not isinstance(j, Expr) or j.den != 1 or j.num < 0: raise PolyError("ValueError| Group function output must be a non-negative integer", [])
		while len(res) < j.num + 1: res.append([])
		res[j.num].append(i)
	return List([List(i) for i in res])


@_register("-.", ['["]'])  # Delete a file
def _(x):
	path = str(x)
	try:
		try: os.remove(path)
		except IsADirectoryError: os.rmdir(path)
	except FileNotFoundError:
		raise PolyError("FileError| File not found: " + path, [])
	except OSError as e:
		raise PolyError("FileError| " + str(e), [])
	return x


@_register("/.", [';'])  # Unix Timestamp (niladic)
def _(null): return Expr(int(time.time() * 10000000), 10000000)
@_register("/.", ['["]'])  # Execute system command
def _(x):
	cmd = str(x)
	return Expr(os.system(cmd))
@_register("/.", ['+'])  # Sleep
def _(x):
	if x.den == 0:
		if x.num == 0: raise PolyError("ValueError| Sleep duration cannot be NaN", [])
		exit(0) # Sleep forever? then exit directly
	else: sleep(x.num / x.den)
	return x


@_register(";.", [])  # Always returns the first argument
def _(*x): return x[0]


INPUT_BUFFER = ""
@_register("<.", [';'])  # Get a character from stdin (niladic)
def _(null):
	global INPUT_BUFFER
	if INPUT_BUFFER == "":
		try: INPUT_BUFFER = input() + "\n"
		except KeyboardInterrupt: raise PolyError("KeyboardInterrupt| Interrupted", [])
		except EOFError: raise PolyError("EOFError| Met end of file in input", [])
	ch = INPUT_BUFFER[0]
	INPUT_BUFFER = INPUT_BUFFER[1:]
	return Char(ch)
@_register("<.", ['["]']) # Get a file's content (always binary mode)
def _(x):
	path = str(x)
	try:
		with open(path, "rb") as f: return List([Expr(b) for b in f.read()])
	except FileNotFoundError:
		raise PolyError("FileError| File not found: " + path, [])
	except OSError as e:
		raise PolyError("FileError| " + str(e), [])
@_register("<.", ['["],[["],["]]']) # HTTP GET
def _(x):
	import urllib.request
	url = str(x.former)
	headers_dict = {}
	if isinstance(x.latter, List):
		for h_item in x.latter.val:
			k = str(h_item.former)
			v = str(h_item.latter)
			headers_dict[k] = v
	try:
		req = urllib.request.Request(url, headers=headers_dict)
		with urllib.request.urlopen(req) as resp:
			return List([Expr(b) for b in resp.read()])
	except urllib.error.URLError as e:
		raise PolyError("NetworkError| " + str(e.reason), [])
	except Exception as e:
		raise PolyError("NetworkError| " + str(e), [])


@_register("=.", ['["]'])  # JSON decoding
def _(x):
	from json import loads
	pyobj = loads(str(x))
	return Polyify(pyobj)
@_register("=.", ['{+|["]|[1.]|[1.],[1.]}'])  # JSON generating
def _(x):
	from json import dumps
	obj = dePolyify(x)
	return List(dumps(obj))


@_register(">.", ['*'])  # Print
def _(x):
	res = yield vmcall("*.", x)
	print(end=str(res))
	return x
@_register(">.", ['*','["]'])  # Print into file or create folder
def _(x, target):
	path = str(target)
	if isinstance(x, Null):
		try:
			os.makedirs(path, exist_ok=True)
			return target
		except OSError as e:
			raise PolyError("FileError| Cannot create directory: " + str(e), [])
	body_bytes = b''
	if isinstance(x, List):
		if len(x.val) > 0 and isinstance(x.val[0], Char):
			body_bytes = str(x).encode('utf-8')
		else:
			for i in x.val:
				if not isinstance(i, Expr) or i.den != 1 or not (0 <= i.num <= 255):
					raise PolyError("ValueError| Binary write data must be integers 0-255", [])
				body_bytes += bytes([i.num])
	else:
		s_list = yield vmcall("*.", x)
		body_bytes = str(s_list).encode('utf-8')
	try:
		with open(path, "wb") as f:
			f.write(body_bytes)
		return x
	except OSError as e:
		raise PolyError("FileError| " + str(e), [])
@_register(">.", ['*','["],[["],["]]'])  # HTTP POST
def _(x, target):
	import urllib.request
	url = str(target.former)
	headers_dict = {}
	if isinstance(target.latter, List):
		for h_item in target.latter.val:
			k = str(h_item.former)
			v = str(h_item.latter)
			headers_dict[k] = v
	body_bytes = b''
	if isinstance(x, List) and isinstance(x.val[0], Expr):
		for i in x.val:
			if not isinstance(i, Expr) or i.den != 1 or not (0 <= i.num <= 255):
				raise PolyError("ValueError| HTTP Body bytes invalid", [])
			body_bytes += bytes([i.num])
	else:
		s_list = yield vmcall("*.", x)
		body_bytes = str(s_list).encode('utf-8')
	try:
		req = urllib.request.Request(url, data=body_bytes, headers=headers_dict, method='POST')
		with urllib.request.urlopen(req) as resp:
			return List([Expr(b) for b in resp.read()])
	except urllib.error.URLError as e:
		raise PolyError("NetworkError| " + str(e.reason), [])
	except Exception as e:
		raise PolyError("NetworkError| " + str(e), [])


@_register("@.", ['[]','>'])  # Prefix reduce
def _(x,f):
	if not x.val: return List([])
	b = x.val[0]
	res = [b]
	for i in x.val[1:]:
		b = yield vmcall(f, b, i)
		res.append(b)
	return List(res)
@_register("@.", ['[]','>','*'])  # Prefix reduce with beginning value
def _(x,f,b):
	res = []
	for i in x.val:
		b = yield vmcall(f, b, i)
		res.append(b)
	return List(res)


@_register("|.", ['[]','>'])  # Drop elements from the end while predicate is true
def _(x,f):
	res = x.val.copy()
	if not res: return List([])
	cond = yield vmcall(f, res[-1])
	while cond:
		res.pop()
		if not res: break
		cond = yield vmcall(f, res[-1])
	return List(res)
@_register("|.", ['*','[]'])  # Join (Insert between each item)
def _(x,f):
	res = []
	for i in f.val:
		res.append(i)
		res.append(x)
	res.pop()
	return List(res)


@_register("~.", ['[]','>'])  # Reduce
def _(x,f):
	if not x.val: return Null
	res = x.val[0]
	for i in x.val[1:]:
		res = yield vmcall(f, res, i)
	return res
@_register("~.", ['[]','>','*'])  # Reduce with beginning value
def _(x,f,b):
	res = b
	for i in x.val:
		res = yield vmcall(f, res, i)
	return res

class Marker: pass

def _swapfuncditer(f, a):
	if not a: return f.l if isinstance(f, dIterator) else f
	if isinstance(f, dIterator) and not (isinstance(f.l, List) or isinstance(f.l, Pair)):
		f, a[0] = f.l, dIterator(a[0], f.r)
	return f, a

class VirtualMachine:
	def __init__(self):
		global stdlib
		self.variables = [stdlib, {}]

		self.fstack = []
		self.estack = []
		self.ip = []
		self.cntstack = []
		self.cntscopes = []
		self.cnttry = []

		self.operands = []

		self.tryptr = []
		self.trystacklen = []
		self.tryscopecnt = []
	def getvar(self, name):
		for i in reversed(self.variables):
			info = i.get(name)
			if info is not None: return info
		if name and name[-1] == '.' and name[-2] != '.':
			structname = name[:-1]
			return _consconsstruct(structname) # Fallback
		return None
	def setvar(self, name, val):
		for i in reversed(self.variables):
			if name in i:
				i[name] = val
				return True
		return False
	def definevar(self, name, val): self.variables[-1][name] = val

	def raiseerror(z, msg, pos=[], returntodepth=0):
		if isinstance(msg, str): msg = List(msg)
		pos = list(pos)
		while len(z.cnttry) > returntodepth and not z.cnttry[-1]:
			z.cnttry.pop()
			z.cntstack.pop(); z.fstack.pop()
			for i in range(z.cntscopes.pop()): z.variables.pop()
			pos.append(z.estack.pop()[z.ip.pop()-1][1])
		if len(z.cnttry) == returntodepth: raise PolyError(msg, pos, AlreadyPoly=True) # Recursion support
		z.cnttry[-1] -= 1
		exceptstacklen = z.trystacklen.pop()
		while len(z.operands) > exceptstacklen: z.operands.pop()
		exceptscopecnt = z.tryscopecnt.pop()
		while len(z.variables) > exceptscopecnt: z.variables.pop(); z.cntscopes[-1] -= 1
		z.ip[-1] = z.tryptr.pop()
		z.definevar("___", msg)

	def call(z, insts, _func=None, _arity=0):
		returntodepth = len(z.estack)
		z.estack.append(insts)
		z.fstack.append(BasicFunc([([],insts)]) if _func is None else _func)
		z.ip.append(0)
		z.cntstack.append(len(z.operands)-_arity)
		z.cntscopes.append(0)
		z.cnttry.append(0)

		while len(z.ip) > returntodepth:
			if z.ip[-1] >= len(z.estack[-1]):
				z.fstack.pop(); z.estack.pop()
				z.ip.pop()
				assert z.cntscopes.pop() == 0
				assert z.cntstack.pop() == len(z.operands) - 1
				assert z.cnttry.pop() == 0
				continue
			inst = z.estack[-1][z.ip[-1]]
			z.ip[-1] += 1
			kind, pos, *args = inst
			if kind == Inst.PUSH: z.operands.append(args[0])
			elif kind == Inst.DUP: z.operands.append(z.operands[-args[0]])
			elif kind == Inst.TAKE:
				z.operands.append(z.operands.pop(-args[0]))
			elif kind == Inst.DROP: z.operands.pop(-args[0])
			elif kind == Inst.INSERT: z.operands.insert(-args[0], z.operands.pop())
			elif kind == Inst.DEFINE: z.definevar(args[0], z.operands.pop())
			elif kind == Inst.GET:
				val = z.getvar(args[0])
				if val is None:
					z.raiseerror("NameError| Name %s is not defined" % args[0], returntodepth=returntodepth)
					continue
				z.operands.append(val)
			elif kind == Inst.SET:
				if z.setvar(args[0], z.operands.pop()) is False:
					z.raiseerror("NameError| Name %s is not defined" % args[0], returntodepth=returntodepth)
					continue
			elif kind == Inst.APPLY:
				arity = args[0]
				for i,j in enumerate(z.operands[-arity-1:]):
					if j is CONT: z.operands[-arity-1+i] = NULL
				a = z.operands[-arity-1:]
				a[-1], a[:-1] = _swapfuncditer(a[-1], a[:-1])
				ranks = [i.r if isinstance(i,dIterator) else [] for i in a]
				indexes = []; s = {}
				for i in range(len(a)):
					if ranks[i]:
						s.setdefault(ranks[i].pop(0),[]).append(i)
				if not s:
					*arg, func = a
					if not isinstance(func, Func):
						z.raiseerror("TypeError| Expected function call, got %s" % stypeof(func), returntodepth=returntodepth)
						continue
					rfunc = func.get(arg)
					if rfunc is None:
						z.raiseerror(("TypeError| No matching overload found for"+" %s"*arity) % tuple(stypeof(i) for i in arg), returntodepth=returntodepth)
						continue
					elif isinstance(rfunc, list):
						# Tail Call Optimization
						z.operands.pop() # Func instance
						z.fstack.append(func)
						z.estack.append(rfunc)
						z.ip.append(0)
						z.cntstack.append(len(z.operands)-arity)
						z.cntscopes.append(0)
						z.cnttry.append(0)
					else: 
						del z.operands[-arity-1:]
						try:
							tmp = rfunc(*arg)
							if not isinstance(tmp, Generator): z.operands.append(tmp)
							else:
								try:
									request = next(tmp)
									while True: request = tmp.send(z.call(request))
								except StopIteration as SI: z.operands.append(SI.value)
						except PolyError as e:
							z.raiseerror(e.args[0], e.args[1], returntodepth=returntodepth)
							continue
				else:
					del z.operands[-arity-1:]
					while s:
						minr = min(s.keys())
						t = s.pop(minr)
						indexes.append(t)
						for i in t:
							if ranks[i]: s.setdefault(ranks[i].pop(0),[]).append(i)
					def _recursive(b, indexes):
						if Marker in b: return b[0]
						if not indexes:
							*arg, func = b
							func, arg = _swapfuncditer(func, arg)
							if not isinstance(func, Func):
								z.raiseerror("TypeError| Expected function call, got %s" % stypeof(func), returntodepth=returntodepth)
								return
							rfunc = func.get(arg)
							if rfunc is None:
								z.raiseerror(("TypeError| No matching overload found for"+" %s"*arity) % tuple(stypeof(i) for i in arg), returntodepth=returntodepth)
								return
							if isinstance(rfunc, list):
								z.operands.extend(arg)
								try: res = z.call(rfunc, func, arity) # Recursion
								except PolyError as e:
									z.raiseerror(e.args[0], e.args[1], returntodepth=returntodepth)
									return
								return res
							else:
								try:
									tmp = rfunc(*arg)
									if not isinstance(tmp, Generator): return tmp
									else:
										try:
											request = next(tmp)
											while True: request = tmp.send(z.call(request))
										except StopIteration as SI: return SI.value
								except PolyError as e:
									z.raiseerror(e.args[0], e.args[1], returntodepth=returntodepth)
									return
						th, *indexes = indexes
						lb = len(b)
						res = []
						try:
							for i in range(len(b[th[0]])):
								c = []
								for j in range(lb):
									if j in th: c.append(b[j][i] if i < len(b[j]) else Marker) # duck typing
									else: c.append(b[j])
								res.append(_recursive(c, indexes))
						except TypeError: z.raiseerror("TypeError| Cannot broadcast on a scalar", returntodepth=returntodepth)
						if None in res: return
						if isinstance(b[th[0]], Pair):
							assert len(res) == 2
							res = Pair(res[0], res[1])
						else: res = List(res)
						return res
					res = _recursive([i.l if isinstance(i,dIterator) else i for i in a], indexes)
					if res is not None: z.operands.append(res)
			elif kind == Inst.CONSITER: z.operands.append(dIterator(z.operands.pop(), [args[0]]))
			elif kind == Inst.LOADLAMBDA:
				typing, body, replidx = args
				body = list(body)
				for i in replidx:
					CLOSURE, pos2, identifier = body[i]
					val = z.getvar(identifier)
					if val is None:
						z.raiseerror("NameError| Name %s is not defined" % identifier, [pos2], returntodepth=returntodepth)
						continue
					body[i] = (CLOSURE, pos2, identifier, val)
				z.operands.append(BasicFunc([(typing, body)]))
			elif kind == Inst.ENTERSCOPE: z.variables.append({}); z.cntscopes[-1] += 1
			elif kind == Inst.EXITSCOPE: z.variables.pop(); z.cntscopes[-1] -= 1
			elif kind == Inst.CLOSURE:
				if len(args) == 2: val = args[1]
				else: val = z.getvar(args[0])
				z.definevar(args[0], val)
				z.operands.append(val)
			elif kind == Inst.JMP: z.ip[-1] += args[0]
			elif kind == Inst.JF:
				val = z.operands.pop()
				if not val: z.ip[-1] += args[0]
			elif kind == Inst.RETURN:
				val = z.operands.pop()
				numscopes = z.cntscopes.pop()
				for i in range(numscopes): z.variables.pop()
				expectedstacklen = z.cntstack.pop()
				while len(z.operands) > expectedstacklen: z.operands.pop()
				trylevel = z.cnttry.pop()
				for i in range(trylevel): z.tryptr.pop(); z.trystacklen.pop(); z.tryscopecnt.pop()
				z.ip.pop(); z.fstack.pop(); z.estack.pop()
				z.operands.append(val)
			elif kind == Inst.TRY:
				z.cnttry[-1] += 1
				z.tryptr.append(z.ip[-1] + args[0])
				z.trystacklen.append(len(z.operands))
				z.tryscopecnt.append(len(z.variables))
			elif kind == Inst.EXCEPT:
				z.ip[-1] += args[0]
				z.cnttry[-1] -= 1
				z.tryptr.pop()
				expectedstacklen = z.trystacklen.pop()
				while len(z.operands) > expectedstacklen + 1: z.operands.pop()
				expectedscopecnt = z.tryscopecnt.pop()
				while len(z.variables) > expectedscopecnt:
					z.variables.pop(); z.cntscopes[-1] -= 1
					if z.cntscopes[-1] == 0: break
			elif kind == Inst.RAISE: z.raiseerror(z.operands.pop(), returntodepth=returntodepth); continue
			elif kind == Inst.RECUR: z.operands.append(z.fstack[-args[0]])
			elif kind == Inst.PUSHMARK: z.operands.append(Marker)
			elif kind == Inst.CONSLIST:
				cnt = -1
				while z.operands[cnt] != Marker:
					if isinstance(z.operands[cnt],dIterator): z.operands[cnt] = z.operands[cnt].l
					if z.operands[cnt] is CONT: z.operands.pop(cnt); cnt += 1
					else: cnt -= 1
				res = List(z.operands[cnt+1:])
				del z.operands[cnt:]
				z.operands.append(res)
			elif kind == Inst.CONSPAIR:
				latter = z.operands.pop()
				former = z.operands.pop()
				if latter is CONT: latter = NULL
				if former is CONT: former = NULL
				z.operands.append(Pair(former,latter))
			elif kind == Inst.EXPANDPAIR:
				val = z.operands.pop()
				if not isinstance(val,Pair):
					z.raiseerror("TypeError| Expected pair, got %s" % stypeof(val), returntodepth=returntodepth)
					continue
				z.operands.append(val.former)
				z.operands.append(val.latter)
			elif kind == Inst.EXPANDLIST:
				val = z.operands.pop()
				if not isinstance(val,List):
					z.raiseerror("TypeError| Expected list, got %s" % stypeof(val), returntodepth=returntodepth)
					continue
				if len(args) == 1:
					if len(val) != args[0]:
						z.raiseerror("ValueError| Incorrect list length to unpack (excepted %d, got %d)" % (args[0],len(val)), returntodepth=returntodepth)
						continue
					for i in val.val: z.operands.append(i)
				else:
					l,prefn,postfn = len(val),args[0],args[1]
					if l < args[0] + args[1]:
						z.raiseerror("ValueError| Incorrect list length to unpack (excepted at least %d, got %d)" % (args[0]+args[1],l), returntodepth=returntodepth)
						continue
					z.operands.extend(val.val[:prefn])
					z.operands.append(List(val.val[prefn:-postfn] if postfn else val.val[prefn:]))
					z.operands.extend(val.val[-postfn:] if postfn else [])
			elif kind == Inst.CONSSTRUCT:
				val = z.operands.pop()
				if len(args) == 0: # destruct
					if not isinstance(val,UserDefinedTypeObject):
						z.raiseerror("TypeError| Expected struct, got %s" % stypeof(val), returntodepth=returntodepth)
						continue
					z.operands.append(val.value)
				else: z.operands.append(UserDefinedTypeObject(args[0], val))  # construct
			elif kind == Inst.COMMUTE:
				val = z.operands.pop()
				if not isinstance(val,Func):
					z.raiseerror("TypeError| Expected function for commute, got %s" % stypeof(val), returntodepth=returntodepth)
					continue
				z.operands.append(CommutedFunc(val, args[0]))
			elif kind == Inst.CONSTRAIN:
				r = z.operands[-args[0]:]
				del z.operands[-args[0]:]
				flag = False
				for i in r:
					if not isinstance(i,Func):
						z.raiseerror("TypeError| Expected function for train, got %s" % stypeof(i), returntodepth=returntodepth)
						flag = True
						break
				if flag: continue
				z.operands.append(Train(r))
			elif kind == Inst.EVAL:
				val = z.operands.pop()
				try: src = "".join(val.val)
				except (TypeError, AttributeError):
					z.raiseerror("TypeError| Expected string for eval, got %s" % stypeof(val), returntodepth=returntodepth)
					continue
				try:
					tokens = tokenize(src, "<string>")
					ast = parse(tokens) # No preprocessing
					ir = []
					for i in ast:
						ir.extend(compile(i))
						ir.append((Inst.DROP,"<string>",1))
					if not ir: ir = [(Inst.PUSH,"<string>",NULL)]
					else: ir.pop()
					z.operands.append(z.call(ir))
				except PolyError as e:
					z.raiseerror(e, returntodepth=returntodepth)
					continue
			else: raise NotImplementedError() # should be unreachable when completed

			
		return z.operands.pop()

def importer(directory):
	with open(directory, "r") as f:
		code = f.read()
		return code

class Environment(VirtualMachine):
	def __init__(self):
		super().__init__()
		self.importer = importer
	def register(self, name, types):
		args = [Type("$"+_+"$") for _ in types]
		def wrapper(f):
			j = self.variables[0].setdefault(name, BasicFunc(name=name))
			j.config(args, f)
			return f
		return wrapper
	def removedef(self, name, types):
		expecttype = [Type("$"+_+"$") for _ in types]
		if name not in self.variables[0]:
			raise ValueError(f"Function not found: {name}")
		overloads = self.variables[0][name].overloads
		for i, j in reversed(list(enumerate(overloads))):
			if j[0] == expecttype:
				del overloads[i]
				return
		raise ValueError(f"Overload not found: {name} with types {types}")

	def hook_include(self, func):
		"""func(source: str) -> str
		   Receives the source text (or path), returns the code string to eval.
		   Pure Python."""
		self.importer = func
		return func

	def hook_stdin(self, func):
		"""func() -> str   (single character, or '' for EOF)"""
		self.removedef("<.", [';'])
		@self.register("<.", [';'])
		def _(null):
			ch = func()
			if ch == '' or ch is None:
				raise PolyError("EOFError| Met end of file in input", [])
			return Char(ch)
		return func

	def hook_stdout(self, func):
		"""func(text: str) -> None"""
		self.removedef(">.", ['*'])
		@self.register(">.", ['*'])
		def _(x):
			res = yield vmcall("*.", x)
			func(str(res))
			return x
		return func

	def hook_filein(self, func):
		"""func(path: str) -> bytes"""
		self.removedef("<.", ['["]'])
		@self.register("<.", ['["]'])
		def _(x):
			path = str(x)
			data = func(path)
			return List([Expr(b) for b in data])
		return func

	def hook_fileout(self, func):
		"""func(path: str, data: bytes | None) -> None
		   If data is None, create directory at path.
		   If data is bytes, write to file at path."""
		self.removedef(">.", ['*','["]'])
		@self.register(">.", ['*','["]'])
		def _(x, target):
			path = str(target)
			if isinstance(x, Null):
				func(path, None)
				return target
			if isinstance(x, List):
				if len(x.val) > 0 and isinstance(x.val[0], Char):
					raw = ''.join(c.val for c in x.val).encode('utf-8')
				else:
					raw = bytearray()
					for i in x.val:
						if not isinstance(i, Expr) or i.den != 1 or not (0 <= i.num <= 255):
							raise PolyError("ValueError| Binary write data must be integers 0-255", [])
						raw.append(i.num)
					raw = bytes(raw)
			else:
				s_list = yield vmcall("*.", x)
				raw = ''.join(c.val for c in s_list.val).encode('utf-8')
			func(path, raw)
			return x
		return func

	def hook_filedel(self, func):
		"""func(path: str) -> None"""
		self.removedef("-.", ['["]'])
		@self.register("-.", ['["]'])
		def _(x):
			func(str(x))
			return x
		return func

	def hook_listdir(self, func):
		"""func(path: str) -> (list[str], list[str])
		   Returns (folder_names, file_names)."""
		self.removedef("%.", ['["]'])
		@self.register("%.", ['["]'])
		def _(x):
			path = str(x)
			folders, files = func(path)
			return Pair(
				List([List(name) for name in folders]),
				List([List(name) for name in files]),
			)
		return func

	def hook_system(self, func):
		"""func(cmd: str) -> int   (exit code)"""
		self.removedef("/.", ['["]'])
		@self.register("/.", ['["]'])
		def _(x):
			return Expr(func(str(x)))
		return func

	def hook_httpget(self, func):
		"""func(url: str, headers: dict[str,str]) -> bytes"""
		self.removedef("<.", ['["],[["],["]]'])
		@self.register("<.", ['["],[["],["]]'])
		def _(x):
			url = str(x.former)
			headers = {}
			if isinstance(x.latter, List):
				for h_item in x.latter.val:
					headers[str(h_item.former)] = str(h_item.latter)
			data = func(url, headers)
			return List([Expr(b) for b in data])
		return func

	def hook_httppost(self, func):
		"""func(url: str, headers: dict[str,str], body: bytes) -> bytes"""
		self.removedef(">.", ['*','["],[["],["]]'])
		@self.register(">.", ['*','["],[["],["]]'])
		def _(x, target):
			url = str(target.former)
			headers = {}
			if isinstance(target.latter, List):
				for h_item in target.latter.val:
					headers[str(h_item.former)] = str(h_item.latter)
			if isinstance(x, List):
				if len(x.val) > 0 and isinstance(x.val[0], Char):
					body = ''.join(c.val for c in x.val).encode('utf-8')
				elif len(x.val) > 0 and isinstance(x.val[0], Expr):
					buf = bytearray()
					for i in x.val:
						if not isinstance(i, Expr) or i.den != 1 or not (0 <= i.num <= 255):
							raise PolyError("ValueError| HTTP Body bytes invalid", [])
						buf.append(i.num)
					body = bytes(buf)
				else:
					body = b''
			else:
				s_list = yield vmcall("*.", x)
				body = ''.join(c.val for c in s_list.val).encode('utf-8')
			data = func(url, headers, body)
			return List([Expr(b) for b in data])
		return func
		
	def assign(self, name, value):
		self.variables[0][name] = value
	def eval(self, code, filename="<repl>"):
		tokens = tokenize(code)
		tokens = preprocess(tokens, self.importer, filename)
		ast = parse(tokens)
		ir = []
		for i in ast:
			ir.extend(compile(i))
			ir.append((Inst.DROP,"<repl>",1))
		if not ir: return NULL
		ir.pop()
		return self.call(ir)

if __name__ == "__main__":
	if len(argv) > 1:
		filepath = normalizePath(argv[1])
		def printHelpAndExit(error_msg=""):
			print("\033[91mERROR: %s\033[0m\nUsage: python Polynomix.py filename.plx\nOr python Polynomix.py to enter the REPL." % error_msg)
			exit(1)
		if not os.path.exists(filepath): printHelpAndExit("File not found")
		if not filepath.endswith(".plx"): printHelpAndExit("Invalid file type")
		with open(filepath, "r", encoding="utf-8") as f: code = f.read()
		env = Environment()
		try:
			result = env.eval(code, filepath)
			if result is not NULL:
				print()
				print("\033[90mprogram exited with return value =", PolyRepr(result), "\033[0m")
			exit(0)
		except PolyError as e:
			msg, traceback = e.args
			print("\033[91mTraceback:")
			for addr in reversed(traceback):
				if isinstance(addr, int):
					lspltdc = code.split('\n')
					ln = code.count("\n",0,addr)
					col = addr - code.rfind("\n",0,addr) - 1
					print("at Line %d, Col %d" % (ln+1, col))
					print("   ", lspltdc[ln][:col] + "\033[95m==>\033[91m" + lspltdc[ln][col:])
				elif isinstance(addr, tuple):
					filename, pos = addr
					print("in File %s, at Pos %d" % (filename, pos))
				else: print("at %s"%addr)
			print(str(msg))
			print(end="\033[0m")
			exit(1)
	# Enter REPL
	print("""\033[90mPolynomix %s | %s | by islptng
Type "!reset" to reset the environment. Press Ctrl+L to prevent your code from being executed.
Press Ctrl+Z then Enter to quit.\033[0m\n""" % (VERSION, LAST_MODIFIED))
	env = Environment()
	@env.hook_stdin
	def _():
		global INPUT_BUFFER
		if not INPUT_BUFFER:
			try: INPUT_BUFFER = input("\033[94m") + "\n"
			except KeyboardInterrupt: raise PolyError("KeyboardInterrupt| Interrupted", [])
			except EOFError: raise PolyError("EOFError| Met end of file in input", [])
		ch, INPUT_BUFFER = INPUT_BUFFER[0], INPUT_BUFFER[1:]
		return ch
	@env.hook_stdout
	def _(s):
		print(end="\033[0m"+s)
	while True:
		try:
			code = input("\033[33m==> \033[97m")
			firstline = True
			while "\x0c" in code:
				code = code.replace("\x0c", "")
				print(("\033[1A\033[2K\033[33m%s \033[97m"+code.split("\n")[-1])%("==." if firstline else "  |"))
				code += "\n" + input("\033[33m  | \033[97m"); firstline = False
		except EOFError: print("\033[0mGoodbye!\n"); exit(0)
		except KeyboardInterrupt: print(); code = ""
		if code == "": print(end = "\033[1A\033[2K"); continue
		if code == "!reset":
			env = Environment()
			print("Environment reset.\n")
			continue
		try: res = env.eval(code)
		except PolyError as e:
			msg, traceback = e.args
			print("\033[91mTraceback:")
			for addr in reversed(traceback):
				if isinstance(addr, int):
					lspltdc = code.split('\n')
					ln = code.count("\n",0,addr)
					col = addr - code.rfind("\n",0,addr) - 1
					print("at Line %d, Col %d" % (ln+1, col))
					print("   ", lspltdc[ln][:col] + "\033[95m==>\033[91m" + lspltdc[ln][col:])
				elif isinstance(addr, tuple):
					filename, pos = addr
					print("in File %s, at Pos %d" % (filename, pos))
				else: print("at %s"%addr)
			print(str(msg))
			print(end="\033[0m")
			res = NULL
		except KeyboardInterrupt: print("\033[91m\nInterrupted\033[0m"); res = NULL
		if not isinstance(res, Null):
			print("\033[30m<= \033[95m" + PolyRepr(res))
		print()