Skip to content

Instantly share code, notes, and snippets.

@DataKinds

DataKinds/genome.py

Last active October 5, 2020 08:21
Show Gist options
  • Save DataKinds/d74971f0e0b5603a124b607616ad84b6 to your computer and use it in GitHub Desktop.
Save DataKinds/d74971f0e0b5603a124b607616ad84b6 to your computer and use it in GitHub Desktop.
Download ZIP
CS homework
Raw
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)))))
"""
Raw
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()
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment