Source

ski / reduce.py

#!/usr/bin/env python

import sys

DEBUG = False
CACHE_THRESHOLD = 15

def logger(x):
	if DEBUG:
		print x

def get_full_term(term_beginning):
	logger('looking for full term in %s' % (term_beginning,))
	balance = 1
	for pos, x in enumerate(term_beginning):
		if balance == 0:
			logger('full term is: ' + term_beginning[:pos])
			return term_beginning[:pos]

		balance += 1 if x == '`' else -1
	
	if balance == 0:
		return term_beginning
	else:
		raise Exception('incomplete term, balance %s' % (balance,))

def reduce_ski(term, cache={}):
	term = get_full_term(term)
	if term[0] != '`':
		return term

	cachable = len(term) < CACHE_THRESHOLD
	if cachable:
		cached = cache.get(term)
		if cached is not None:
			return cached

	if term[:2] == '`i':
		logger('reducing (`i rule): %s' % (term,))
		result = reduce_ski(term[2:])
		if cachable:
			cache[term] = result
		return result

	if term[:3] == '``k':
		logger('reducing (``k rule): %s' % (term,))
		result = reduce_ski(term[3:])
		if cachable:
			cache[term] = result
		return result

	if term[:4] == '```s':
		logger('reducing (```s rule): %s' % (term,))
		x = get_full_term(term[4:])
		total_len = 4+len(x)
		y = get_full_term(term[total_len:])
		total_len += len(y)
		z = get_full_term(term[total_len:])
		total_len += len(z)
		result = reduce_ski('``%s%s`%s%s' % (x, z, y, z))
		if cachable:
			cache[term] = result
		return result

	x = get_full_term(term[1:])
	l = reduce_ski(x)
	y = get_full_term(term[1+len(x):])
	if x != l:
		logger('reducing left: %s' % (term,))
		result = reduce_ski('`%s%s' % (l, y))
		if cachable:
			cache[term] = result
		return result

	r = reduce_ski(y)
	if y != r:
		new = '`%s%s' % (x, r)
		logger('reducing right: %s to %s' % (term, new))
		result = reduce_ski(new)
		if cachable:
			cache[term] = result
		return result

	if cachable:
		cache[term] = term
	return term

if __name__ == "__main__":
	inp = sys.argv[1]
	print reduce_ski(get_full_term(inp))