CS homework

genome.py

"""
Filename: genome.py
Author:   Tyler
Purpose:  Construct phylogenetic trees.
"""

# ;; Consider this my final hoorah before dropping my CS major.
# ;; https://xkcd.com/224/

code="""
(defun -kgram-string-to-set (k str set)
  (if (> k (length str))
    set
    (-kgram-string-to-set k (substr str 1 (length str)) (set->add set (substr str 0 k)))))

(defun kgram-string-to-set (k str)
  (-kgram-string-to-set k str (set->new)))

(defun genome-to-genome-with-set (genome)
  (hashmap->set genome "genome" (kgram-string-to-set N (hashmap->get genome "genome"))))

(defun jaccard (k set1 set2)
  (let ((union (set->union set1 set2))
        (intersection (set->intersection set1 set2)))
    (/ (length intersection) (length union))))

(defun genome-to-genome-set (genome)
  (hashmap->get genome "genome"))

(defun genome-to-id (genome)
  (hashmap->get genome "id"))

(defun genome-jaccard (k genome1 genome2)
  (jaccard k (genome-to-genome-set genome1) (genome-to-genome-set genome2)))

(defun max (x y)
  (if (> x y)
    x
    y))
(defun min (x y)
  (if (< x y)
    x
    y))

(defun -genome-to-tree-distance (k genome phylo largest)
  (let ((head (car phylo))
        (tail (cdr phylo)))
    (let ((head-largest (if (= (type head) "Quote")
                          (max (-genome-to-tree-distance k genome head largest) largest)
                          (max (genome-jaccard k genome head) largest))))
      (if (= (type tail) "Quote")
        (max (-genome-to-tree-distance k genome tail largest) head-largest)
        head-largest))))

(defun genome-to-tree-distance (k genome phylo)
  (-genome-to-tree-distance k genome phylo 0))

(defun -tree-distance (k phylo1 phylo2 largest)
  (let ((head (car phylo1))
        (tail (cdr phylo1)))
    (let ((head-largest (if (= (type head) "Quote")
                          (max (-tree-distance k head phylo2 largest) largest)
                          (max (genome-to-tree-distance k head phylo2) largest))))
      (if (= (type tail) "Quote")
        (max (-tree-distance k tail phylo2 largest) head-largest)
        head-largest))))

(defun tree-distance (k phylo1 phylo2)
  (-tree-distance k phylo1 phylo2 0))


(defun init-phylogenetic-tree-list ()
  (map list (map genome-to-genome-with-set FASTA-LIST)))

(defun -get-highest-similarity (phylo1 full-phylo-list1 phylo2 highest)
  (let ((head1 (car phylo1))
        (tail1 (cdr phylo1))
        (head2 (car phylo2))
        (tail2 (cdr phylo2)))
    (if (= head1 head2)
      (-get-highest-similarity tail1 full-phylo-list1 phylo2 highest)
      (if (= tail1 NIL)
        (if (= tail2 NIL)
          highest
          (max highest (-get-highest-similarity full-phylo-list1 full-phylo-list1 tail2 highest)))
        (max highest (max (tree-distance N head1 head2) (-get-highest-similarity tail1 full-phylo-list1 phylo2 highest)))))))

(defun get-highest-similarity (phylo-list)
  (if (> 2 (length phylo-list))
    0
    (-get-highest-similarity phylo-list phylo-list phylo-list 0)))

(defun -tree-of-similarity (phylo1 full-phylo-list1 phylo2 similarity)
  (let ((head1 (car phylo1))
        (tail1 (cdr phylo1))
        (head2 (car phylo2))
        (tail2 (cdr phylo2)))
    (if (= head1 head2)
      (-tree-of-similarity tail1 full-phylo-list1 phylo2 similarity)
      (let ((similarity-cond (tree-distance N head1 head2)))
        (if (= similarity-cond similarity)
          (cons head1 (list head2))
          (if (= tail1 NIL)
            (if (= tail2 NIL)
              (print "This should never happen! -tree-of-similarity returned NIL. You passed a faulty similarity value!")
              (-tree-of-similarity full-phylo-list1 full-phylo-list1 tail2 similarity))
            (-tree-of-similarity tail1 full-phylo-list1 phylo2 similarity)))))))

(defun tree-of-similarity (phylo-list similarity)
  (-tree-of-similarity phylo-list phylo-list phylo-list similarity))

(defun remove-from-list (phylo-list item)
  (if (= phylo-list NIL)
    NIL
    (if (= item (car phylo-list))
      (remove-from-list (cdr phylo-list) item)
      (cons (car phylo-list) (remove-from-list (cdr phylo-list) item)))))

(defun phylo-list-iteration (phylo-list)
  (let ((highest-similarity (get-highest-similarity phylo-list))
        (new-phylo-tree (tree-of-similarity phylo-list highest-similarity))
        (once-pruned-phylo-list (remove-from-list phylo-list (car new-phylo-tree)))
        (twice-pruned-phylo-list (remove-from-list once-pruned-phylo-list (cadr new-phylo-tree))))
    (cons new-phylo-tree twice-pruned-phylo-list)))

(defun iterate-phylo-list (phylo-list)
  (let ((iterated (phylo-list-iteration phylo-list)))
    (if (> 2 (length iterated))
      iterated
      (iterate-phylo-list iterated))))

(defun str-quote-of-phylogenetic-tree (phylo-quote)
  (if (= (cadr phylo-quote) NIL)
    (str-phylogenetic-tree (car phylo-quote))
    (let ((half1 (str-phylogenetic-tree (car phylo-quote)))
          (half2 (str-phylogenetic-tree (cadr phylo-quote))))
      (concat "(" (min half1 half2) ", " (max half1 half2) ")"))))
(defun str-value-of-phylogenetic-tree (phylo-value)
  (if (= phylo-value NIL)
    "NIL"
    (genome-to-id phylo-value)))
(defun str-phylogenetic-tree (phylo-tree)
  (if (= (type phylo-tree) "Quote")
    (str-quote-of-phylogenetic-tree phylo-tree)
    (str-value-of-phylogenetic-tree phylo-tree)))

(print (str-phylogenetic-tree (car (iterate-phylo-list (init-phylogenetic-tree-list)))))
"""

phylo.py

"""
Filename: phylo.py
Author:   Tyler
Purpose:  Print out phylogenetic trees of genomes
"""
# TESTER NOTE: This program _may_ run out of memory, smash the python recursion limit,
#   eat up all the CPU cycles, time out, etc, etc. It is correct for all cases, but
#   simply has awful overhead -- calling a function in the written Lisp dialect has
#   non-negligible overhead, and the entire program operates on naive recursion. Thus,
#   I've never actually been able to finish testing test cases 3 through 5.
#
#   I did, however, do some very aggressive profiling throughout the development process.
#   Unfortunately, the bottlenecks are largely something that I'm simply going to have to
#   deal with. Namely, they're the `copy()` functions on `SExpr` and `Value` that slow the
#   program down the most. Alas, the woes of dynamic scripting languages...

# Hey, Angel... I got tired of writing in Python.
# You really don't have to grade this. You can if you want,
# and if you do, please just ignore the contents of `tree.py`.
# It's not pretty. In fact, it's over 1000 lines of absolute
# horror that no man should deserve to read. I've hidden a few
# fun comments throughout should you happen to make the trek, though.

import tree
import fractions
import genome

def parse_fasta_block(block):
    """
    Parses a long string representing a FASTA
        formatted genome.

    Parameters:
        block -- the FASTA genome

    Returns:
        a hash map representing the genome
    """
    lines = block.split("\n")
    id = lines[0][1:].split()[0]
    genome = "".join(lines[1:])
    return {"id": tree.Value(tree.Value.String, id), "genome": tree.Value(tree.Value.String, genome)}

def main():
    """
    The main entry point of the program
    """
    filename = input("FASTA file: ")
    try:
        n = fractions.Fraction(input("n-gram size: "))
    except:
        tree.fatal_error("Bad value for N")
    try:
        fasta_file = open(filename)
    except:
        tree.fatal_error("could not open file {}".format(filename))

    # Initialize the Lisp runtime
    main_runtime = tree.Runtime()
    main_runtime.register_variable("N", tree.Value(tree.Value.Number, n))
    fasta_list = tree.SExpr(None, None)
    fasta_list_ptr = fasta_list
    fastas = fasta_file.read()
    for fasta in fastas.split("\n\n"):
        if fasta.strip() != "":
            fasta_list_ptr._car = tree.Value(tree.Value.Hashmap, parse_fasta_block(fasta))
            fasta_list_ptr._cdr = tree.SExpr(None, None)
            fasta_list_ptr = fasta_list_ptr.cdr()
    # prune the final empty SExpr
    snd_ptr = fasta_list
    while snd_ptr != None:
        if snd_ptr.cdr() == tree.SExpr(None, None):
            snd_ptr._cdr = None
            break
        snd_ptr = snd_ptr.cdr()
    main_runtime.register_variable("FASTA-LIST", tree.Value(tree.Value.Quote, fasta_list))

    # Finally, run the code!
    main_runtime.evaluate_parser(tree.SExprParser(tree.SExprLexer(genome.code)))

main()

tree.py

"""
Filename: tree.py
Author:   Tyler
Purpose:  Provide a tree structure to interact with
    the rest of the program.
Note:     This Lisp implementation is very incomplete!
    Functionality-wise, the CL hyperspec was used as a
    reference throughout the writing of this Lisp.
"""
import fractions
import sys
from abc import ABC, abstractmethod
import copy
import sys
sys.setrecursionlimit(1000000000)

def fatal_error(string):
    """
    Helper function to print an error and die.

    Parameters:
        string -- the string to print out
    """
    print("ERROR: {}".format(string))
    sys.exit(1)

def arg_error(string):
    """
    Helper function to print an error and die.

    Parameters:
        string -- the string to print out
    """
    print("ARGUMENT ERROR: {}".format(string))
    sys.exit(1)

def var_error(string):
    """
    Helper function to print an error and die.

    Parameters:
        string -- the string to print out
    """
    print("VARIABLE ERROR: {}".format(string))
    sys.exit(1)

# Since the UA turnin system doesn't allow multiple
# file uploads, here's how I'm sectioning this code:
#############################################
# BEGIN LEX/PARSE-TIME CODE                 #
#############################################

class Token:
    """
    Represents a parse-time Lisp token.
    """
    # Uninhabited values
    OpenParen = "OpenParen"
    CloseParen = "CloseParen"
    Quote = "Quote"
    Nil = "Nil"
    # Inhabited values
    Number = "Number"
    Ident = "Ident"
    String = "String"

    def __init__(self, tag, value):
        """
        Initializes a `Token`

        Parameters:
            tag -- the type of token to initialize. The only valid values
                for this parameter are the tags listed above this function.
            value -- the value this token contains (only valid for inhabited values,
                pass in None otherwise).
        """
        assert tag in [Token.OpenParen, Token.CloseParen, Token.Quote, Token.Number, Token.Ident, Token.String, Token.Nil]
        self._tag = tag
        if tag in [Token.OpenParen, Token.CloseParen, Token.Quote, Token.Nil]:
            assert value == None
        self._value = value

    def tag(self):
        """
        Getter for self._tag

        Returns:
            a string, self._tag
        """
        return self._tag
    def value(self):
        """
        Getter for self._value

        Returns:
            self._value
        """
        return self._value
    def __str__(self):
        """
        Formats this `Token` as a printable string, mostly for debugging.

        Returns:
            a string representing this token
        """
        return "[{}: {}]".format(self._tag, self._value)

class SExprLexer:
    def __init__(self, program):
        """
        Initializes an `SExprLexer`.

        Parameters:
            program -- a string, representing lisp code
        """
        self._program = program

    def preformat(self):
        """
        Formats the string in a nice way for the lexer to handle.
        """
        # Remove all newlines
        self._program = self._program.replace("\n", "")
        # Trim all spaces down to 1 single space (dirty hack)
        self._program = " ".join(self._program.split())

    def next(self):
        """
        Gets the next token out of the token stream. This mutates the
            `SExprLexer` object.

        Returns:
            a `Token` representing the next token in the stream,
                or None if there are no tokens left.
        """
        # return None if program is exhausted
        if len(self._program) == 0:
            return None
        # skip whitespace
        while self._program[0].isspace():
            self._program = self._program[1:]
            # return None if program is exhausted
            if len(self._program) == 0:
                return None
        # parse single character tokens
        if self._program[0] == "(":
            self._program = self._program[1:]
            return Token(Token.OpenParen, None)
        elif self._program[0] == ")":
            self._program = self._program[1:]
            return Token(Token.CloseParen, None)
        elif self._program[0] == "'":
            self._program = self._program[1:]
            return Token(Token.Quote, None)
        else:
            # parse multi character tokens
            if self._program[0] == "\"":
                # string parsing
                # pop the current double quote
                self._program = self._program[1:]
                token_string = ""
                while len(self._program) > 0 and self._program[0] != "\"":
                    token_string = token_string + self._program[0]
                    self._program = self._program[1:]
                # pop the final quote
                # NOTE: this line fails if a string is unterminated by the end of the program
                self._program = self._program[1:]
                return Token(Token.String, token_string)
            elif self._program[0].isdigit() or (self._program[0] == "-" and self._program[1].isdigit()):
                # number parsing
                number_string = ""
                # pop off the minus sign if it exists
                if self._program[0] == "-":
                    number_string = "-"
                    self._program = self._program[1:]
                while len(self._program) > 0 and (self._program[0].isdigit() or self._program[0] == "."):
                    number_string = number_string + self._program[0]
                    self._program = self._program[1:]
                # NOTE: this line (silently?) fails if the number contains multiple decimal points
                return Token(Token.Number, fractions.Fraction(number_string))
            else:
                # ident/nil parsing
                ident_string = ""
                while len(self._program) > 0 and not self._program[0].isspace() and not self._program[0] in "()" :
                    ident_string = ident_string + self._program[0]
                    self._program = self._program[1:]
                if ident_string == "NIL":
                    return Token(Token.Nil, None)
                else:
                    return Token(Token.Ident, ident_string)

class SExprParser:
    def __init__(self, lexer):
        """
        Initializes an `SExprParser`.

        Parameters:
            lexer -- a `SExprLexer` to use to get a token stream
        """
        self._lexer = lexer
        self._lexer.preformat()

    def parse_token_list(tl):
        """
        Local function to aid in recursion in parsing
            token lists to sexprs.

        Parameters:
            tl -- a list of `Token`s

        Returns:
            an `SExpr`, or None if the SExpr is empty
        """
        # Remove the parens from either end of the token list
        tl_content = tl[1:-1]
        if len(tl_content) == 0:
            # Base case: if there are no more tokens, end the s-expression
            return None

        car = None
        if tl_content[0].tag() == Token.OpenParen:
            # if the first bit of the token list has an open paren (AKA it is an expression in and of itself),
            # then we gotta parse it recursively
            recursive_car_tl = [tl_content[0]]
            tl_content = tl_content[1:]
            paren_depth = 1
            while paren_depth > 0:
                if tl_content[0].tag() == Token.OpenParen:
                    paren_depth += 1
                elif tl_content[0].tag() == Token.CloseParen:
                    paren_depth -= 1
                recursive_car_tl.append(tl_content[0])
                tl_content = tl_content[1:]
            car = SExprParser.parse_token_list(recursive_car_tl)
        elif tl_content[0].tag() == Token.CloseParen:
            fatal_error("Unreachable parse.")
        elif tl_content[0].tag() == Token.Quote:
            # Pop the quote off
            tl_content = tl_content[1:]
            # Then make sure it was an S-expression that was quoted
            if tl_content[0].tag() != Token.OpenParen:
                fatal_error("Cannot quasiquote a non-expression.")
            # If we're good, just parse an s-expression like normal
            recursive_car_tl = [tl_content[0]]
            tl_content = tl_content[1:]
            paren_depth = 1
            while paren_depth > 0:
                if tl_content[0].tag() == Token.OpenParen:
                    paren_depth += 1
                elif tl_content[0].tag() == Token.CloseParen:
                    paren_depth -= 1
                recursive_car_tl.append(tl_content[0])
                tl_content = tl_content[1:]
            car = Value(Value.Quote, SExprParser.parse_token_list(recursive_car_tl))
        elif tl_content[0].tag() == Token.Number:
            car = Value(Value.Number, tl_content[0].value())
            tl_content = tl_content[1:]
        elif tl_content[0].tag() == Token.Nil:
            car = Value(Value.Nil, None)
            tl_content = tl_content[1:]
        elif tl_content[0].tag() == Token.Ident:
            car = Value(Value.Ident, tl_content[0].value())
            tl_content = tl_content[1:]
        elif tl_content[0].tag() == Token.String:
            car = Value(Value.String, tl_content[0].value())
            tl_content = tl_content[1:]
        return SExpr(car, SExprParser.parse_token_list([Token(Token.OpenParen, None)] + tl_content + [Token(Token.CloseParen, None)]))

    def parse_one_full_sexpr(self):
        """
        Pops n tokens from the stream until matching parens are found,
            then parse the entire compiled list of tokens as one sexpr.

        Returns:
            a `SExpr` object or `None` if there are no more expressions to parse
        """
        token_list = [self._lexer.next()]
        if token_list[0] == None:
            return None
        elif token_list[0].tag() != Token.OpenParen:
            fatal_error("Bare {} at the top level.".format(str(token_list[0].tag())))
        paren_depth = 1
        while paren_depth > 0:
            next_token = self._lexer.next()
            if next_token == None:
                fatal_error("Unclosed S-expression before EOF.")
            elif next_token.tag() == Token.OpenParen:
                paren_depth += 1
            elif next_token.tag() == Token.CloseParen:
                paren_depth -= 1
            token_list.append(next_token)
        return SExprParser.parse_token_list(token_list)


#############################################
# BEGIN RUN-TIME CODE                       #
#############################################
class Value:
    """
    Represents a run-time Lisp data value.
    """
    # Uninhabited types
    Nil = "Nil"
    # Inhabited types
    Number = "Number"
    Ident = "Ident"
    String = "String"
    Quote = "Quote"
    Set = "Set"
    Hashmap = "Hashmap"

    def __init__(self, tag, value):
        """
        Initializes a `Value`

        Parameters:
            tag -- the type of value to initialize. The only valid values
                for this parameter are the tags listed above this function.
            value -- the value this `Value` contains
        """
        assert tag in [Value.Number, Value.Ident, Value.String, Value.Quote, Value.Nil, Value.Set, Value.Hashmap]
        self._tag = tag
        if tag != Value.Nil:
            assert value != None
        self._value = value

    def tag(self):
        """
        Getter for self._tag

        Returns:
            a string, self._tag
        """
        return self._tag
    def value(self):
        """
        Getter for self._value

        Returns:
            self._value
        """
        return self._value
    def __eq__(self, other):
        """
        Define equality as comparison on inner values.

        Returns:
            a boolean
        """
        return (type(self) == type(other)) and (self.value() == other.value())
    def __hash__(self):
        """
        Define hashing as hashing on inner values.

        Returns:
            a boolean
        """
        return hash(self.value())
    def __str__(self):
        """
        Returns a string representation of this `Value`

        Returns:
            str(self._value)
        """
        if self.tag() == Value.Nil:
            return "NIL"
        elif self.tag() == Value.Quote:
            return "'({})".format(str(self._value))
        elif self.tag() == Value.Hashmap:
            s = ""
            for key, val in self.value().items():
                s += "{}: {}, ".format(str(key), str(val))
            return "{"+s+"}"
        else:
            return str(self._value)
    def copy(self):
        """
        Returns a copy of itself

        Returns:
            a `Value`
        """
        return Value(self.tag(), self.value())

class SExpr:
    """
    Represents an S-expression.
    """
    def __init__(self, car, cdr):
        """
        Initializes an `SExpr`. Diagram:
            https://en.wikipedia.org/wiki/S-expression#/media/File:Corrected_S-expression_tree_2.png

        Parameters:
            car -- the head value in the sexpr
                (either a bare `Value` or another `SExpr`)
            cdr -- the rest of the sexpr tree
                (either a `SExpr` or None)

        """
        self._car = car
        self._cdr = cdr

    def car(self):
        """
        Getter for the car attribute

        Returns:
            see initializer
        """
        return self._car
    def cdr(self):
        """
        Getter for the cdr attribute

        Returns:
            see initializer
        """
        return self._cdr
    def __str__(self):
        """
        Converts an `SExpr` to a Lisp string

        Returns:
            a string
        """
        if type(self._car) == Value:
            if self._cdr == None:
                return "{}".format(str(self._car))
            else:
                return "{} {}".format(str(self._car), str(self._cdr))
        elif type(self._car) == SExpr:
            if self._cdr == None:
                return "({})".format(str(self._car))
            else:
                return "({} {})".format(str(self._car), str(self._cdr))
        elif self._car == None:
            return "()"
    def __eq__(self, other):
        """
        Define equality on `SExpr`s as comparing contents

        Parameters:
            other -- the other thing to compare

        Returns:
            a boolean
        """
        try:
            return (self.car() == other.car()) and (self.cdr() == other.cdr())
        except:
            return False
    def copy(self):
        """
        Returns a copy of itself

        Returns:
            a `SExpr`
        """
        out = SExpr(None, None)
        if self.car() != None:
            out._car = self.car().copy()
        if self.cdr() != None:
            out._cdr = self.cdr().copy()
        return out

class PyDefinition(ABC):
    """
    Abstract class representing a Python function definition
    """
    @abstractmethod
    def run(runtime, expr):
        """
        Execute the unimplemented Python function

        Parameters:
            expr -- in the case of a PyMacro, an unevaluated expr
                in the case of a PyFunction, an evaluated expr
        Returns:
            in the case of a PyFunction: a `Value`
            In the case of a PyMacro: a `SExpr`
        """
        pass

class RuntimeDefinition:
    """
    Encapsulates a function/macro/variable definition.
    """
    Function = "Function"
    Macro = "Macro"
    Variable = "Variable"
    PyFunction = "PyFunction"
    PyMacro = "PyMacro"

    def __init__(self, name, switch, def_):
        """
        Initializes a `RuntimeDefinition`.

        Parameters:
            name -- a string, the name of the definition
            switch -- RuntimeDefinition.Function, RuntimeDefinition.Macro, RuntimeDefinition.Variable, RuntimeDefinition.PyFunction, RuntimeDefinition.PyMacro
            def_ --   a `SExpr`                   a `SExpr`                a `Value`                   a `PyDefinition`              a `PyDefinition`
        """
        self._name = name
        assert switch in [RuntimeDefinition.Function, RuntimeDefinition.Macro, RuntimeDefinition.Variable, RuntimeDefinition.PyFunction, RuntimeDefinition.PyMacro]
        self._switch = switch
        if switch in [RuntimeDefinition.Function, RuntimeDefinition.Macro]:
            assert type(def_) == SExpr
        elif switch in [RuntimeDefinition.Variable]:
            assert type(def_) == Value
        elif switch in [RuntimeDefinition.PyFunction, RuntimeDefinition.PyMacro]:
            assert PyDefinition in def_.mro()
        self._def = def_

    def name(self):
        """
        Getter for the name attribute

        Returns:
            a string, self._name
        """
        return self._name
    def switch(self):
        """
        Getter for the switch attribute

        Returns:
            a string, self._switch
        """
        return self._switch
    def def_(self):
        """
        Getter for the def attribute

        Returns:
            see initializer
        """
        return self._def

# "Does it ever end?"
# "No. Does that even matter?
# Show up anyway."
# ~~ a haiku by an anonymous author
#############################################
# BEGIN RUN-TIME FUNCTION DEFINTIONS        #
#############################################
# Arithmetic
class LispAdd(PyDefinition):
    """
    Addition
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if val.tag() != Value.Number:
                arg_error("Cannot add values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() + fix(expr.cdr())
        return Value(Value.Number, fix(expr))

class LispSubtract(PyDefinition):
    """
    Subtraction
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if val.tag() != Value.Number:
                arg_error("Cannot subtract values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() - fix(expr.cdr())
        return Value(Value.Number, fix(expr))

class LispMultiply(PyDefinition):
    """
    Multiplication
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if val.tag() != Value.Number:
                arg_error("Cannot multiply values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() * fix(expr.cdr())
        return Value(Value.Number, fix(expr))

class LispDivide(PyDefinition):
    """
    Division
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if val.tag() != Value.Number:
                arg_error("Cannot divide values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() / fix(expr.cdr())
        return Value(Value.Number, fix(expr))

# Comparisons
class LispLessThan(PyDefinition):
    """
    Less than
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if not val.tag() in [Value.Number, Value.String]:
                arg_error("Cannot divide values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() < fix(expr.cdr())
        if fix(expr):
            return Value(Value.Number, 1)
        else:
            return Value(Value.Number, 0)

class LispGreaterThan(PyDefinition):
    """
    Greater than
    """
    def run(runtime, expr):
        def fix(expr):
            val = expr.car()
            if not val.tag() in [Value.Number, Value.String]:
                arg_error("Cannot divide values of type {}".format(val.tag()))
            if expr.cdr() == None:
                return val.value()
            else:
                return val.value() > fix(expr.cdr())
        if fix(expr):
            return Value(Value.Number, 1)
        else:
            return Value(Value.Number, 0)

class LispEqualTo(PyDefinition):
    """
    Equal to
    """
    def run(runtime, expr):
        def fix(expr):
            # TODO: this breaks with > 2 arguments
            val = expr.car()
            if expr.cdr() == None:
                return val
            else:
                return val == fix(expr.cdr())
        if fix(expr):
            return Value(Value.Number, 1)
        else:
            return Value(Value.Number, 0)

# Bindings
class LispDefun(PyDefinition):
    """
    Function definition
    """
    def run(runtime, expr):
        try:
            name = expr.car()
            # abuse of python's short circuiting
            if type(name) == Value and name.tag() == Value.Ident:
                pass
            else:
                arg_error("Cannot name function using type {}.".format(name.tag()))
            # TODO: check the types of args & body
            args = expr.cdr().car()
            body = expr.cdr().cdr()
        except:
            arg_error("Not enough arguments to `defun`.")
        runtime.register_function(name.value(), args, body)
        return SExpr(None, None)

class LispLet(PyDefinition):
    """
    Let bindings (sequential)
    """
    def run(runtime, expr):
        try:
            var_forms = expr.car()
            expr_forms = expr.cdr()
        except:
            arg_error("Not enough args passed to `let`.")
        # lexical_scope = copy.deepcopy(runtime)
        lexical_scope = runtime
        # establish the bindings in the let scope
        curr_var_pair = var_forms
        while curr_var_pair != None:
            curr_var_name = curr_var_pair.car().car()
            curr_var_def = curr_var_pair.car().cdr().car()
            if curr_var_name.tag() != Value.Ident:
                arg_error("Cannot bind to a value of type {}.".format(curr_var_name.tag()))
            # evaluate the definition, if it happens to be an expression and not a value
            if type(curr_var_def) == SExpr:
                curr_var_def = lexical_scope.evaluate_sexpr(curr_var_def)
            # then do the bindings!
            lexical_scope.register_variable(curr_var_name.value(), curr_var_def)
            curr_var_pair = curr_var_pair.cdr()
        # then execute the rest of the forms and return the final value
        curr_expr = expr_forms
        while curr_expr != None:
            out = lexical_scope.evaluate_sexpr(curr_expr.car())
            curr_expr = curr_expr.cdr()
        return SExpr(Value(Value.Ident, "const"), SExpr(out, None))

class LispProg(PyDefinition):
    """
    Prog notation
    """
    def run(runtime, expr):
        out = expr
        while out.cdr() != None:
            out = out.cdr()
        return out.car()

class LispConst(PyDefinition):
    """
    Constant function (always returns its first argument)
    """
    def run(runtime, expr):
        try:
            return expr.car()
        except:
            arg_error("No args passed to `const`.")

# Print
class LispPrint(PyDefinition):
    """
    Print
    """
    def run(runtime, expr):
        try:
            if expr.car().tag() == Value.Set:
                # Python's default Set stringification is bad
                strs = []
                for item in expr.car().value():
                    strs.append(str(item))
                print("{",end="")
                print(str(strs),end="")
                print("}")
            else:
                print(str(expr.car()))
        except:
            print()
        try:
            return expr.car()
        except:
            return Value(Value.Nil, None)

class LispPrintNNL(PyDefinition):
    """
    Print (no newline)
    """
    def run(runtime, expr):
        try:
            if expr.car().tag() == Value.Set:
                # Python's default Set stringification is bad
                strs = []
                for item in expr.car().value():
                    strs.append(str(item))
                print("{",end="")
                print(str(strs),end="")
                print("}", end="")
            else:
                print(str(expr.car()),end="")
        except:
            print(end="")
        try:
            return expr.car()
        except:
            return Value(Value.Nil, None)

# Conditionals
class LispIf(PyDefinition):
    """
    If/else statement
    """
    def run(runtime, expr):
        try:
            cond = expr.car()
            if type(cond) != SExpr:
                arg_error("If condition must be an S-expression, not a {}.".format(cond.tag()))
            truthy = expr.cdr().car()
            falsy = expr.cdr().cdr().car()
        except:
            arg_error("Not enough arguments to `if`.")
        # run the condition
        cond_value = runtime.evaluate_sexpr(cond)
        # TODO: implement real booleans
        if cond_value.tag() != Value.Number:
            arg_error("Condition returned a non-number value.")
        # branch
        followed_branch = None
        if cond_value.value() != 0:
            followed_branch = truthy
        else:
            followed_branch = falsy
        if type(followed_branch) == SExpr:
            return followed_branch
        else:
            return SExpr(Value(Value.Ident, "const"), SExpr(followed_branch, None))

# Generic data manipulation
class LispLength(PyDefinition):
    """
    Length
    """
    def run(runtime, expr):
        if expr.car() == None:
            arg_error("Nothing passed to `length`.")
        val = expr.car()
        if val.tag() in [Value.String, Value.Set, Value.Hashmap]:
            return Value(Value.Number, fractions.Fraction(len(val.value())))
        elif val.tag() == Value.Quote:
            n = 0
            ptr = val.value()
            while ptr != None:
                n += 1
                ptr = ptr.cdr()
            return Value(Value.Number, fractions.Fraction(n))
        elif val.tag() == Value.Nil:
            return Value(Value.Number, 0)
        else:
            arg_error("Cannot take the length of type {}".format(val.tag()))

class LispType(PyDefinition):
    """
    Type
    """
    def run(runtime, expr):
        return Value(Value.String, expr.car().tag())

# Working with Lists
class LispCar(PyDefinition):
    """
    Car
    """
    def run(runtime, expr):
        if not expr.car().tag() in [Value.Quote, Value.Nil]:
            arg_error("Cannot take `car` of type {}".format(expr.car().tag()))
        if expr.car().tag() == Value.Nil:
            return Value(Value.Nil, None)
        out = expr.car().value().car()
        if out == None:
            return Value(Value.Nil, None)
        else:
            return out

class LispAt(PyDefinition):
    """
    At
    """
    def run(runtime, expr):
        quote = expr.car()
        n = expr.cdr().car()
        if not quote in [Value.Quote, Value.Nil]:
            arg_error("Cannot take `at` of type {}".format(expr.car().tag()))
        if quote.tag() == Value.Nil:
            return Value(Value.Nil, None)
        out_ptr = quote.value()
        for out_ptr in range(n.value()):
            out_ptr = out_ptr.cdr()
            if out_ptr == None:
                return Value(Value.Nil, None)
        if type(out_ptr.car()) == SExpr:
            return Value(Value.Quote, out_ptr.car())
        else:
            return out_ptr.car()

class LispCdr(PyDefinition):
    """
    Cdr
    """
    def run(runtime, expr):
        if not expr.car().tag() in [Value.Quote, Value.Nil]:
            arg_error("Cannot take `cdr` of type {}".format(expr.car().tag()))
        if expr.car().tag() == Value.Nil:
            return Value(Value.Nil, None)
        out = expr.car().value().cdr()
        if out == None:
            return Value(Value.Nil, None)
        else:
            return Value(Value.Quote, out)

class LispCadr(PyDefinition):
    """
    Cadr
    """
    def run(runtime, expr):
        if expr.car().tag() != Value.Quote:
            arg_error("Cannot take `car` of type {}".format(expr.car().tag()))
        try:
            out = expr.car().value().cdr().car()
            if out == None:
                return Value(Value.Nil, None)
            else:
                return out
        except:
            return Value(Value.Nil, None)

class LispCons(PyDefinition):
    """
    Cons
    """
    def run(runtime, expr):
        try:
            car = expr.car()
            cdr = expr.cdr().car()
        except:
            arg_error("Not enough arguments to `cons`")
        if cdr.tag() == Value.Quote:
            return Value(Value.Quote, SExpr(car, cdr.value()))
        if cdr.tag() == Value.Nil:
            return Value(Value.Quote, SExpr(car, None))
        else:
            # this is a bizarre case but okay, Lisp.
            return Value(Value.Quote, SExpr(car, cdr))

class LispList(PyDefinition):
    """
    List
    """
    def run(runtime, expr):
        out = SExpr(None, None)
        out_ptr = out
        curr_expr_ptr = expr
        while curr_expr_ptr != None:
            out_ptr._car = curr_expr_ptr.car()
            if curr_expr_ptr.cdr() != None:
                out_ptr._cdr = SExpr(None, None)
                out_ptr = out_ptr.cdr()
            else:
                out_ptr._cdr = None
            curr_expr_ptr = curr_expr_ptr.cdr()
        return Value(Value.Quote, out)

class LispMap(PyDefinition):
    """
    Map a list
    Since our lisp doesn't have anonymous functions
        (or even really first class functions at all),
    we pass around identifiers to other functions.
    """
    def run(runtime, expr):
        try:
            ident = expr.car()
            quote = expr.cdr().car()
        except:
            arg_error("Not enough arguments to `map`")
        if ident.tag() != Value.Ident:
            arg_error("Expected Ident, got {}.".format(ident.tag()))
        if quote.tag() != Value.Quote:
            arg_error("Expected Quote, got {}.".format(quote.tag()))
        to_be_mapped = quote.value()
        to_be_mapped_ptr = to_be_mapped
        while to_be_mapped_ptr != None:
            to_be_mapped_ptr._car = runtime.evaluate_sexpr(SExpr(ident, SExpr(to_be_mapped_ptr.car(), None)))
            to_be_mapped_ptr = to_be_mapped_ptr.cdr()
        return Value(Value.Quote, to_be_mapped)

# Working with Sets
class LispInitSet(PyDefinition):
    """
    Create a new set
    """
    def run(runtime, expr):
        return Value(Value.Set, set())

class LispAddSet(PyDefinition):
    """
    Add a value to a set
    """
    def run(runtime, expr):
        try:
            set = expr.car()
            val = expr.cdr().car()
        except:
            arg_error("Not enough arguments passed to `set->add`.")
        if set.tag() != Value.Set:
            arg_error("Expected Set, got {}".format(val.tag()))
        bare_set = set.value()
        bare_set.add(val)
        return Value(Value.Set, bare_set)

class LispIntersectSet(PyDefinition):
    """
    Find the intersection between two sets
    """
    def run(runtime, expr):
        try:
            set1 = expr.car()
            set2 = expr.cdr().car()
        except:
            arg_error("Not enough arguments passed to `set->add`.")
        if set1.tag() != Value.Set:
            arg_error("Expected Set, got {}".format(val.tag()))
        if set2.tag() != Value.Set:
            arg_error("Expected Set, got {}".format(val.tag()))
        return Value(Value.Set, set1.value().intersection(set2.value()))

class LispUnionSet(PyDefinition):
    """
    Find the union between two sets
    """
    def run(runtime, expr):
        try:
            set1 = expr.car()
            set2 = expr.cdr().car()
        except:
            arg_error("Not enough arguments passed to `set->add`.")
        if set1.tag() != Value.Set:
            arg_error("Expected Set, got {}".format(val.tag()))
        if set2.tag() != Value.Set:
            arg_error("Expected Set, got {}".format(val.tag()))
        return Value(Value.Set, set1.value().union(set2.value()))

# Working with Hashmaps
class LispInitHashmap(PyDefinition):
    """
    Create a new hashmap
    """
    def run(runtime, expr):
        return Value(Value.Hashmap, {})

class LispSetHashmap(PyDefinition):
    """
    Set a value in a hash map
    """
    def run(runtime, expr):
        try:
            hashmap = expr.car()
            key = expr.cdr().car()
            val = expr.cdr().cdr().car()
        except:
            arg_error("Not enough arguments passed to `hashmap->set`.")
        if not key.tag() in [Value.String, Value.Number]:
            arg_error("Cannot take the hash of type {}".format(val.tag()))
        if hashmap.tag() != Value.Hashmap:
            arg_error("Expected Hashmap, got {}".format(val.tag()))
        bare_hashmap = hashmap.value()
        bare_hashmap[key.value()] = val
        return Value(Value.Hashmap, bare_hashmap)

class LispGetHashmap(PyDefinition):
    """
    Get a value in a hash map
    """
    def run(runtime, expr):
        try:
            hashmap = expr.car()
            key = expr.cdr().car()
        except:
            arg_error("Not enough arguments passed to `hashmap->get`.")
        if not key.tag() in [Value.String, Value.Number]:
            arg_error("Cannot take the hash of type {}".format(key.tag()))
        if hashmap.tag() != Value.Hashmap:
            arg_error("Expected Hashmap, got {}".format(hashmap.tag()))
        return hashmap.value()[key.value()]

# Working with Strings
class LispSubstring(PyDefinition):
    """
    Get a substring of a string
    """
    def run(runtime, expr):
        try:
            string = expr.car()
            index1 = expr.cdr().car()
            index2 = expr.cdr().cdr().car()
        except:
            arg_error("Not enough arguments passed to `substr`.")
        if string.tag() != Value.String:
            arg_error("Expected String, got {}.".format(string.tag()))
        if index1.tag() != Value.Number:
            arg_error("Expected Number, got {}.".format(index1.tag()))
        if index2.tag() != Value.Number:
            arg_error("Expected Number, got {}.".format(index2.tag()))
        if index1.value().denominator != 1 or index2.value().denominator != 1:
            arg_error("Expected integers for `substr`.")
        return Value(Value.String, string.value()[int(index1.value()):int(index2.value())])

class LispConcat(PyDefinition):
    """
    Get a substring of a string
    """
    def run(runtime, expr):
        out = ""
        ptr = expr
        while ptr != None:
            if type(ptr.car()) != Value:
                arg_error("Expected String, got expression.")
            if ptr.car().tag() != Value.String:
                arg_error("Expected String, got {}.".format(ptr.car().tag()))
            out += ptr.car().value()
            ptr = ptr.cdr()
        return Value(Value.String, out)

class LispSplit(PyDefinition):
    """
    Split a string on a delimiter
    """
    def run(runtime, expr):
        try:
            string = expr.car()
            delim = expr.cdr().car()
        except:
            arg_error("Not enough arguments passed to `substr`.")
        if string.tag() != Value.String:
            arg_error("Expected String, got {}.".format(string.tag()))
        if delim.tag() != Value.String:
            arg_error("Expected String, got {}.".format(delim.tag()))
        split_string = string.value().split(delim.value())
        out_list = SExpr(None, None)
        curr_list_ptr = out_list
        for chunk in split_string:
            curr_list_ptr._car = Value(Value.String, chunk)
            curr_list_ptr._cdr = SExpr(None, None)
            curr_list_ptr = curr_list_ptr.cdr()
        return Value(Value.Quote, out_list)
#############################################
# END RUN-TIME FUNCTION DEFINTIONS          #
#############################################

class Runtime:
    def __init__(self):
        # functions AND macros
        self._functions = {}
        self._variables = {}
        # Arithmetic
        self.register_pyfunction("+", LispAdd)
        self.register_pyfunction("-", LispSubtract)
        self.register_pyfunction("*", LispMultiply)
        self.register_pyfunction("/", LispDivide)
        # Comparisons
        self.register_pyfunction("<", LispLessThan)
        self.register_pyfunction(">", LispGreaterThan)
        self.register_pyfunction("=", LispEqualTo)
        # Bindings
        self.register_pymacro("defun", LispDefun)
        self.register_pymacro("let", LispLet)
        self.register_pyfunction("prog", LispProg)
        self.register_pyfunction("const", LispConst)
        # Print
        self.register_pyfunction("print", LispPrint)
        self.register_pyfunction("print-nnl", LispPrintNNL)
        # Conditionals
        self.register_pymacro("if", LispIf)
        # Generic data manipulation
        self.register_pyfunction("length", LispLength)
        self.register_pyfunction("type", LispType)
        # Working with lists
        self.register_pyfunction("car", LispCar)
        self.register_pyfunction("at", LispAt)
        self.register_pyfunction("cdr", LispCdr)
        self.register_pyfunction("cadr", LispCadr)
        self.register_pyfunction("cons", LispCons)
        self.register_pyfunction("list", LispList)
        self.register_pyfunction("map", LispMap)
        # Working with Sets
        self.register_pyfunction("set->new", LispInitSet)
        self.register_pyfunction("set->add", LispAddSet)
        self.register_pyfunction("set->intersection", LispIntersectSet)
        self.register_pyfunction("set->union", LispUnionSet)
        # Working with Hashmaps
        self.register_pyfunction("hashmap->new", LispInitHashmap)
        self.register_pyfunction("hashmap->set", LispSetHashmap)
        self.register_pyfunction("hashmap->get", LispGetHashmap)
        # Working with Strings
        self.register_pyfunction("substr", LispSubstring)
        self.register_pyfunction("concat", LispConcat)
        self.register_pyfunction("split", LispSplit)


    def register_pyfunction(self, name, klass):
        """
        Register a native python function in the runtime

        Parameters:
            name -- a string, the name of the function
            klass -- the name of the `PyDefinition` class
        """
        self._functions[name] = RuntimeDefinition(name, RuntimeDefinition.PyFunction, klass)
    def register_pymacro(self, name, klass):
        """
        Register a native python macro in the runtime

        Parameters:
            name -- a string, the name of the macro
            klass -- the name of the `PyDefinition` class
        """
        self._functions[name] = RuntimeDefinition(name, RuntimeDefinition.PyMacro, klass)
    def register_function(self, name, args, body):
        """
        Register a lisp function in the runtime

        Parameters:
            name -- a string, the name of the function
            args -- a `SExpr` listing the names of the arguments
            body -- an `SExpr`, the body of the function
        """
        self._functions[name] = RuntimeDefinition(name, RuntimeDefinition.Function, SExpr(args, body))
    def register_macro(self, name, args, body):
        """
        Register a lisp macro in the runtime

        Parameters:
            name -- a string, the name of the macro
            args -- a `SExpr` listing the names of the arguments
            body -- an `SExpr`, the body of the function
        """
        self._functions[name] = RuntimeDefinition(name, RuntimeDefinition.Macro, SExpr(args, body))
    def register_variable(self, name, value):
        """
        Register a lisp variable in the runtime

        Parameters:
            name -- a string, the name of the variable
            value -- a `Value`, the value of the variable
        """
        self._variables[name] = value
    def resolve_variable(self, var_name):
        """
        Resolve a variable name in this runtime

        Parameters:
            var_name -- a string, the name of the variable

        Returns:
            a `Value`
        """
        if var_name in self._variables:
            return self._variables[var_name]
        elif var_name in self._functions:
            return Value(Value.Ident, var_name)
        else:
            var_error("Variable {} not found.".format(var_name))


    def evaluate_sexpr(self, ext_expr):
        """
        Evaluate an s-expression in the context
            of this runtime.

        Parameters:
            expr -- the `SExpr` to evaluate

        Returns:
            a `Value`
        """
        # check for missing function/strange type errors up front
        if ext_expr == None:
            return None
        expr = ext_expr.copy()

        func_name_value = expr.car()
        if func_name_value == None:
            # if we're looking at an empty sexpr
            return Value(Value.Nil, None)
        if type(func_name_value) != Value:
            fatal_error("Cannot call expression {} as a function.".format(str(func_name_value)))
        if func_name_value.tag() != Value.Ident:
            fatal_error("Cannot call value {} as a function.".format(str(func_name_value)))
        func_name = func_name_value.value()
        if not func_name in self._functions:
            fatal_error("Cannot find function {}.".format(func_name))
        func_definition = self._functions[func_name]

        # fully evaluate all the arguments of a function
        # also, replace the variables with their values
        if func_definition.switch() in [RuntimeDefinition.Function, RuntimeDefinition.PyFunction]:
            curr_cdr = expr.cdr()
            while curr_cdr != None:
                # evaluate sexprs
                if type(curr_cdr.car()) == SExpr:
                    curr_cdr._car = self.evaluate_sexpr(curr_cdr.car())
                # evaluate variables
                elif type(curr_cdr.car()) == Value and curr_cdr.car().tag() == Value.Ident:
                    curr_cdr._car = self.resolve_variable(curr_cdr.car().value())
                curr_cdr = curr_cdr.cdr()

        # begin evaluating the s-expressions
        # evaluate functions
        if func_definition.switch() == RuntimeDefinition.Function:
            func_args = func_definition.def_().car()
            func_def = func_definition.def_().cdr()

            # this is an awful way to do it
            # I'm sorry Angel, if you read this far
            # copying the entire runtime is _bad_
            # but I don't want to write a copy constructor
            lexical_scope = Runtime()
            lexical_scope._functions = self._functions
            lexical_scope._variables = copy.copy(self._variables)
            # register the arguments as variables in the lexical scope of the function
            curr_arg_value = expr.cdr()
            curr_arg_name = func_args
            while curr_arg_value != None:
                lexical_scope.register_variable(curr_arg_name.car().value(), curr_arg_value.car())
                curr_arg_value = curr_arg_value.cdr()
                curr_arg_name = curr_arg_name.cdr()
                if curr_arg_name == None and curr_arg_value != None:
                    arg_error("Too many arguments passed to {} in expression\n\t{}".format(str(expr.car()), str(expr)))
                elif curr_arg_value == None and curr_arg_name != None:
                    arg_error("Too few arguments passed to {} in expression\n\t{}".format(str(expr.car()), str(expr)))
            # actually call the function, then return the output of the final expression
            curr_expr = func_def
            while curr_expr != None:
                out = lexical_scope.evaluate_sexpr(curr_expr.car())
                curr_expr = curr_expr.cdr()
            return out
            # TODO: remerge the sets of variables at the end
        # evaluate macros
        elif func_definition.switch() == RuntimeDefinition.Macro:
            fatal_error("TODO")
        # evaluate native functions
        elif func_definition.switch() == RuntimeDefinition.PyFunction:
            return func_definition.def_().run(self, expr.cdr())
        # evaluate native macros
        elif func_definition.switch() == RuntimeDefinition.PyMacro:
            o = func_definition.def_().run(self, expr.cdr())
            return self.evaluate_sexpr(o)
    def evaluate_parser(self, parser):
        """
        Exhaust an `SExprParser`, evaluating it in its entirety.

        Parameters:
            parser -- an `SExprParser`
        """
        current_eval = self.evaluate_sexpr(parser.parse_one_full_sexpr())
        while current_eval != None:
            current_eval = self.evaluate_sexpr(parser.parse_one_full_sexpr())

# Today, I have won.
# But tomorrow, I may lose.
# Both days, keep pushing.
# ~~ a haiku by an anonymous author