Saturday, March 25, 2017

Fixing `ImportError: No module named _ssl` while building Python from source in Ubuntu

This is just a reminder in case I ever come across this issue again.

Upon switching my Laptop's OS back to Ubuntu 16.04 today, I re-installed Python 3.6. Then I tried to pip install a module, and I found that the library ssl had a problem. The solution was, quite simply, to install libssl-dev (apparently this doesn't ship with Ubuntu), then rebuild Python 3.6.

Saturday, March 18, 2017

Automate content inclusion after a certain date in LaTeX

While writing my resume in \(\LaTeX\) there were several events I wanted to add, but only after a certain date. Also, I don't want to wait until that date to include them; I want to type them up now, while I have time.

After a little research, I came across pgfcalendar. This page was probably the most helpful in describing its contents/functionality. It allows you to perform some action after, before, or on a certain date, in addition to a bunch of other things.

I've written the following macro utilizing this package. As an example date, we'll use PyCon (because I'm really hoping to be able to attend).

%              YYYY-MM-DD

  \pgfcalendarifdate{\year-\month-\day}{at least=#1}
  {#2}  % if true
  {#3}  % if false
We may use this command as follows.
    \href{}{PyCon},\ \ Portland,\ \ Oregon -- May,\ \ 2017
I've also added an executable bash script to my crontab to re-compile it daily with pdflatex, so it's always up-to-date.

Tuesday, March 14, 2017

Iterators and Iterables in Python 3

Lately I've been examining the difference between iterators and iterables in Python more closely. There's a subtle but distinct difference between the two that's easy to overlook (or simply ignore); however, most every time you've typed a for-loop, such as for i in [1, 2, 3, 4, 5]: print(i), you've used both an iterable and an iterator.

According to the Python 3.6 documentation, iterator types define special methods __iter__ and __next__. Together these form something in Python called the iterator protocol. Moreover, __iter__ typically just returns self, so we only have to worry about writing a definition for __next__. While already contains an abstract Iterator base class (see e.g., instead of importing it I'm going to write it as follows.
from abc import abstractmethod
from typing import Any

class Iterator:
    # c.f. PEP 234, PEP 322

    def _state(self) -> None:
        raise NotImplementedError

    def _state(self, value: Any) -> None:
        raise NotImplementedError

    def __iter__(self) -> 'Iterator':
        return self

    def __next__(self) -> Any:
        raise NotImplementedError
Iterator types are lazy[1] and thus only cough up a value when we ask them to (with the keyword next), so I've added an abstract _state property, to be defined more thoroughly in a subclass (this could just be as simple as a field variable though).

Now, a simple iterator example might look as follows.
class SimpleIterator(Iterator):
    def __init__(self, start: int =0, stop: int =10) -> None:
        self._state = start
        self.stop = stop

    def _state(self) -> int:
        return self.__state

    def _state(self, value: int) -> None:
        self.__state = value

    def __next__(self) -> int:
        if self._state >= self.stop:
            raise StopIteration
            val = self._state
            self._state += 1
            return val

if __name__ == '__main__':
    itr = SimpleIterator()
    for value in itr:

    # prints 0 ... 9
Note that, when this iterator type raises StopIteration, it continues to do so; i.e., calling next(itr) at any point in the future will raise StopIteration. We can convince ourselves of this with a simple brute-force unittest.
from unittest import main, TestCase

class TestIterator(TestCase):

    def setUp(self) -> None:
        self.itr = SimpleIterator()

    def test_stop_iteration(self) -> None:
        # Run iterator to the end
        for item in self.itr: pass
        # Check to see if it raises StopIteration a hundred times or so
        for _ in range(100):
            with self.assertRaises(StopIteration):


# ----------------------------------------------------------------------
# Ran 1 test in 0.002s
# OK
Also, it's not necessary for an iterator to terminate, so the following is fine too.
class SimpleInfiniteIterator(Iterator):
    def __init__(self) -> None:
        self._state = 0

    def _state(self) -> int:
        return self.__state

    def _state(self, value: int) -> None:
        self.__state = value

    def __next__(self) -> int:
        """ Just keep adding one """
        val = self._state
        self._state += 1
        return val
Because a non-terminating iterator never raises a StopIteration, the for-loop continues indefinitely (and hence we don't have to worry about testing that it continues to raise such an exception as it never raises it in the first place).

So that's an iterator. Now what's an iterable? And how is it related to iterators?

From what I've found online, I think the most distinct difference is that iterable types can't be exhausted. In other words, every time a for-loop calls iter(iterable), it gets a fresh new iterator. That's why the following code sample doesn't raise any exceptions.
>>> X = list(range(10))
>>> last = X[-1]
>>> # Loop over X multiple times and print its contents
>>> for _ in range(3):
...     for i in X:
...         print(i, end=', ' if i != last else '\n')
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
In this case, we're looping over a list referenced by X three times. Now, let's try overriding list's __iter__ method so that it cycles over items in the list.
class CyclicIterator(SimpleInfiniteIterator):
    """ Another cyclic iterator that shadows `itertools.cycle`
    (inherits from SimpleInfiniteIterator to avoid some boilerplate

    def __init__(self, some_list: 'CyclicList') -> None:
        self.some_list = some_list

    def __next__(self) -> int:
        val = self._state
        self._state += 1
        self._state %= len(self.some_list)
        return self.some_list[self._state]

class CyclicList(list):

    def __iter__(self) -> Iterator:
        return CyclicIterator(self)

# X = CyclicList([1, 2, 3, 4, 5])
# for i in X: print(i)
# prints 1 ... 5 repeatedly
This seems a little strange, however, because I've passed a reference to the iterator (also, my use of __getitem__ on list to get values).


Sunday, March 12, 2017

RX Algorithm in C

Earlier this year I was trying to learn more C by working on a project formerly left over from drone club. After a couple weeks of toiling with memory leaks (Valgrind is an awesome tool), I finally came up with an implementation of the RX algorithm that's almost fast enough to be useful on a drone for basic anomaly detection.

The code is hosted on GitHub, and I welcome suggestions for improvements as C is definitely not my first language. I suspect there are many memory improvements that could be made; nevertheless, it can compute the Mahalanobis metric on one million RGB vectors in about 1/5 of a second.

As a test, I created the following video from data collected by Terry Sims. Even 4K frames only take about 2s to compute on my modest laptop.
The hardest part was probably figuring out how to read images from disk with libpng. I mostly read through the example.c file to understand how this library works.

I understand now that file specifications/formats are extremely intricate and specific, i.e. every single byte has a meaning, and it's easy to misinterpret that meaning if the functions aren't configured correctly.

Saturday, February 25, 2017

Playing with monads in Python, 1

There are a number of topics in computer science that I have on my list of `stuff to understand at some point'. One of them is monads, which originally perplexed me when I came across Peter Thatcher's article about a year ago.

My favorite way to structure the code is to start with a base class Monad, which requires any subclass (type of monad we're defining, that is) to define methods bind and unit.
from abc import abstractmethod
from types import FunctionType as Function

class Monad:

    def bind(self, f: Function) -> 'Monad':
        raise NotImplementedError

    def __rshift__(self, f: Function) -> 'Monad':
        return self.bind(f)

    def unit(cls, *args) -> 'Monad':
        raise NotImplementedError
As Thatcher wrote in his own implementation, I've overloaded the special method __rshift__ to mean bind, which gets us closer to Haskell's syntax (>>=).

I liked Boyer's SimpleMonad [1], so we'll play with that. All it basically does it store a value. In the following I've also added the special method __eq__ to compare values between two instances of SimpleMonad, and a getter.
class SimpleMonad(Monad):
    """ A really simple monad """
    def __init__(self, x: int) -> None:
        self.x = x

    def bind(self, f: Function) -> 'SimpleMonad':
        return f(self.x)

    def unit(cls, value: int) -> 'SimpleMonad':
        return cls(value)

    def get_value(self) -> int:
        return self.x

    def __eq__(self, other: 'SimpleMonad') -> bool:
        """ Only for tests """
        return self.get_value() == other.get_value()
Now we can define two example actions as follows.
def xor(x: int) -> SimpleMonad:
    return SimpleMonad(x ^ 2)

def digits(x: int) -> SimpleMonad:
    return SimpleMonad(len(str(x)))
We can operate upon an integer in the monadic context using bind
value1 = SimpleMonad(5).bind(xor).bind(digits)
print(value1.get_value())  # 1
and we can also write this as
value2 = SimpleMonad(7) >> xor >> digits
print(value2.get_value())  # 1
Most sources I've read have mentioned that in order for a type to be a monadic type it must satisfy certain ``laws'', but they don't usually list or discuss them. However, for my own understanding, I wanted to show that SimpleMonad is indeed a monad, so I wrote the following tests.
from typing import Any

def check_laws(monad: Any, value: Any, fun1: Function, fun2: Function) -> None:
    name = monad.__name__

    # Left identity
    assert monad.unit(value) >> fun1 == fun1(value), \
        name + ' does not satisfy left identity axiom'

    # Right identity
    assert monad(value) >> monad.unit == monad(value), \
        name + ' does not satisfy right identity axiom'

    # Associativity
    assert ((monad(value) >> fun1) >> fun2) == (monad(value) >> (lambda v: fun1(v) >> fun2)), \
        name + ' does not satisfy associativity'

    print('** All tests passed for ' + name)

if __name__ == '__main__':
    check_laws(SimpleMonad, 6, lambda x: SimpleMonad(x + 6), lambda x: SimpleMonad(x - 1))

    # ** All tests passed for SimpleMonad
EDIT: I also want to talk a little about another monad I use every day: the list monad. I came across an excellent article on a wiki about Haskell that describes this monad and the types of bind and unit, and wrote the following class (vide quoque multiple inheritance).
from typing import Iterable

class ListMonad(list, Monad):

    ## Define `bind` and `unit` for `list` type so it can be passed to `check_laws`

    def bind(self, f: Function) -> 'ListMonad':
        for i, value in enumerate(self):
            self[i] = f(value)[0]    # basically `concat (map f xs)` in Haskell
        return self

    def unit(cls, item: Iterable) -> 'ListMonad':
        return cls([item])
Now, actions as follows can act upon the list's elements.
def double(x: int) -> 'ListMonad':
    return ListMonad([2 * x])

def divider(x: int) -> 'ListMonad':
    return ListMonad([x // 2])
And again, this list doesn't have to contain objects of type int, it could be any type, and these functions could perform any operation upon that type. If I've done everything correctly, the following indicates this is indeed a monad as well.
check_laws(ListMonad, list(range(1)), lambda x: ListMonad([2 * x]), lambda x: ListMonad([x + 1]))

# ** All tests passed for ListMonad
I've also come across an interesting thread on SO discussing Python's context managers as monads; that is, Python's with-statement. However, some answers suggest it may be too general to be a monad. It's an interesting thought, however, because in Haskell IO isn't possible without monads. It's obvious that Python is not a pure functional language, but there seem to be blurred boundaries when it comes to many concepts.

Additional Resources

[1] Super Quick Intro to Monads, by Stephen Boyer
[2] Monads and Gonads, Google Tech Talk by Douglas Crockford

Tuesday, February 21, 2017

Professional Developer Tools for Students from JetBrains

If you're a student like me, you should definitely head over to JetBrains' site and sign up for their free professional developer pack. It grants you a year-long subscription to their products.

I've downloaded both PyCharm and CLion, and I look forward to using the latter more frequently. I've enjoyed using Vim, but the benefits of using these IDEs are that they teach you about the language as you're going along. PyCharm doesn't catch every bug in my code, but it catches nearly all minor issues, and many mid-level package issues too. I hope CLion will help as I learn more about C too.

Saturday, February 11, 2017

Clean simple FITS data

This won't be a lengthy discussion about methods to clean amateur astronomical FITS data; instead, since I've written about it before (albeit when I didn't know very much about Python), I'd rather post some new code I wrote to do the same process in a much clearer way.

#! /usr/bin/env python3.6
# -*- coding: utf-8 -*-

""" Reduce a quick batch of FITS data. Currently run with input file list
-o _Finished_Feb_08_2016

from typing import Generator, Tuple
from import fits as FITS
from import Header as HDU
from argparse import ArgumentParser
from glob import iglob
from datetime import datetime
import numpy as np

_EXT = 'fits'

def get_fits_file(name: str, axis: int =0) -> Tuple[np.ndarray, HDU]:
    """ Get both np.ndarray of data and the HDU (these are simple data) """
    with as image:
        file = image[axis]
        return, file.header

def _get_median_dark_frame(darks: Generator[str, None, None]) -> np.ndarray:
    collective = list(zip(*map(get_fits_file, darks)))
    return np.median(collective[0], axis=0)

def _get_master_flat_frame(flats: Generator[str, None, None]) -> np.ndarray:
    collective = list(zip(*map(get_fits_file, flats)))

    # Get absolute mean of frames and scale them
    for frame in collective[0]:
        frame /= np.mean(frame)

    return np.median(collective[0], axis=0)

def clean(args) -> None:
    """ Process data, just a straightforward pipeline """
    lights, flats, darks = args.lights, args.flats, args.darks
    master_dark = _get_median_dark_frame(darks)
    master_flat = _get_master_flat_frame(flats)

    for light in lights:
        light_data, light_header = get_fits_file(light)
        light_data -= master_dark    # undo additive noise
        light_data /= master_flat    # undo convolution with PSF

        # Now write these data with the new name
        new_name = ''.join(light.split('.')[:-1]) + args.output + '.' + _EXT
        light_header['HISTORY'] = f'Dark subtracted and flat corrected {}'
        FITS.writeto(new_name, light_data, light_header, overwrite=True)

if __name__ == '__main__':
    parser = ArgumentParser(description=__doc__)
    parser.add_argument('-o', '--output', type=str,
        help='Base string of output file name')

    # Positional argument requiring a list of files
    parser.add_argument('lights', type=iglob,
        help='List of input files')

    # Another requiring darks
    parser.add_argument('darks', type=iglob,
        help='List of input dark frames')

    # Another requiring flats
    parser.add_argument('flats', type=iglob,
        help='List of input flat frames')

    args = parser.parse_args()
    del parser
It creates master dark and flat frames with get_median_dark_frame and get_master_flat_frame, then computes the following for each light \(F_{i}\): $$ I_{i}=\dfrac{F_{i}-\mathscr{D}}{\mathscr{F}}. $$ I've written it as a command line tool with argparse so it can be called in a Bash script.

Saturday, January 14, 2017

Making GUIs with Gtk+ in Python

While I was looking through old scripts the other day I came across one that produces a visual verification of Gauss' Circle Problem with Matplotlib. I thought it'd be fun to wrap it in a simple GUI with buttons to re-plot with different radii! The result is the following class.
#! /usr/bin/env python3.4
# -*- coding: utf-8 -*-

""" Main application--embed Matplotlib figure in window with UI """

import gi
gi.require_version('Gtk', '3.0')

import numpy as np
from gi.repository import Gtk, GObject
from matplotlib.figure import Figure

# make sure cairocffi is installed, pycairo doesn't support FigureCanvasGTK3Agg
from matplotlib.backends.backend_gtk3agg import FigureCanvasGTK3Agg \
    as FigureCanvas

from matplotlib.patches import Ellipse
from typing import List, Tuple, Union
from math import sqrt

class Main(Gtk.Window):
    """ Main window UI """
    SIGMA = 10
    INVERT = -1

    def __init__(self) -> None:
        Gtk.Window.__init__(self, title='Gauss\' Circle Problem')
        self.connect('destroy', lambda _: Gtk.main_quit())
        self.set_default_size(650, 500)

        # Set up the l/r box layout = Gtk.Box(spacing=10)

        # Set up the right column
        self.rcolumn = Gtk.VBox(spacing=0)
        self.rcolumn.set_spacing(10), False, False, 20)

        # Set up spin button
        adjustment = Gtk.Adjustment(self.SIGMA, 1, 30, 1, 0, 0)
        self.spinbutton = Gtk.SpinButton()
        self.rcolumn.pack_start(self.spinbutton, False, False, 0)

        # Set up invert checkbox
        self.invertbutton = Gtk.CheckButton('Invert')
        self.invertbutton.connect('toggled', self.switch_toggle_parity, 'invert')

        # Set up update button
        self.update_plot_button = Gtk.Button(label='Update')
        self.update_plot_button.connect('clicked', self.update_sigma_event)


    def calculate(self) -> None:
        """ Re-calculate using the formula """
        arr = np.zeros([self.SIGMA * 2 + 1] * 2)

        points = self.collect(int(self.SIGMA), int(self.SIGMA), self.SIGMA)

        # flip pixel value if it lies inside (or on) the circle
        for p in points:
            arr[p] = 1

        # plot ellipse on top of boxes to show their centroids lie inside
        circ = Ellipse(
            xy=(int(self.SIGMA), int(self.SIGMA)),
            width=2 * self.SIGMA,
            height=2 * self.SIGMA,
        circ.set_facecolor((1, 1, 1)), 2 * self.SIGMA + 0.5), 2 * self.SIGMA + 0.5)

        # Plot the pixel centers*zip(*points), marker='.',
            color='white' if self.INVERT == -1 else 'black')

        # now plot the array that's been created * arr, interpolation='none', cmap='gray')

    def initial_plot(self) -> None:
        """ Set up the initial plot; only called once """
        self.fig = Figure(figsize=(5, 4))
        self.canvas = FigureCanvas(self.fig), True, True, 0) = self.fig.add_subplot(111, aspect='equal')

    def update_sigma_event(self, button: Union[Gtk.Button, None] =None) -> None:
        """ Update sigma and trigger a replot """
        self.SIGMA = int(self.spinbutton.get_value())

    def switch_toggle_parity(self, button: Union[Gtk.CheckButton, None] =None,
            name: str ='') -> None:
        """ Switch the parity of the plot before update """
        self.INVERT *= -1

    def draw_plot(self) -> None:
        """ Draw or update the current plot """

    def collect(x: int, y: int, sigma: float =3.0) -> List[Tuple[int, int]]:
        """ create a small collection of points in a neighborhood of some 
        neighborhood = []

        X = int(sigma)
        for i in range(-X, X + 1):
            Y = int(pow(sigma * sigma - i * i, 1/2))
            for j in range(-Y, Y + 1):
                neighborhood.append((x + i, y + j))

        return neighborhood

if __name__ == '__main__':
    window = Main()
And the following is what the window looks like.

Again, it's not pretty, but so far it works! Improvements I'm hoping to make include grouping the buttons in the right bar together (vertically) and adding a very simple menu bar at the top that allows you to save the current plot; an info button in the sub-menu might be cool too.

Although this is almost nothing like writing GUIs in Java (which require knowledge of many more OOP concepts), it definitely felt like I was writing a traditional Python class while I was working on this.

Thursday, January 12, 2017

Accepting usernames and passwords

I'm working on a terminal application that connects to a MySQL db/server and has a few methods to manipulate data and make requests. Here's a nifty little code byte I've written to accept usernames and passwords.
#! /usr/bin/env python3.4
# -*- coding: utf-8 -*-

""" Test the login decorator I've written in """

from types import FunctionType # I wish Function were in `typing`
from typing import Any
from time import sleep

def login(f: FunctionType) -> FunctionType:
    """ Force user to login """
    def _force_new_f(*args, **kwargs) -> Any:
        _username = input('Enter your username: ')
        _password = input('Enter a password: ')

        while (not _username) or (not _password):
            print('** Please enter a valid password and username')
            _username = input('Enter your username: ')
            _password = input('Enter a password: ')

        # TODO: Here, some function using regex to prevent code injection

        return f(username=_username, password=_password, *args, **kwargs)
    return _force_new_f

class Input:
    __INFO_CHECKED_ = False

    def set_info(self, username: str ='', password: str ='') -> None:
        """ Get password and  """
        self.__username = username
        self.__password = password
        # Call some internal log-in function
        self.__INFO_CHECKED_ = True

    def check_info(self, username: str ='', password: str ='') -> bool:
        """ Re-check password and username """
        if self.__INFO_CHECKED_:
            if username == self.__username and password == self.__password:
                return True
            return False
            raise PermissionError('** Must log in first')

    # Following only here for example and tests

    def get_username(self) -> str:
        return self.__username

    def get_password(self) -> str:
        return self.__password

if __name__ == '__main__':
    io = Input()
I've made the @login decorator so that I can apply it in a few different classes. For example, if I want a particular method to request a username and password again, despite having them already, to make sure they match (much in the same way most popular social media websites ask you for your username and password again before you can delete your account). I'm open to ideas regarding clearer and simpler ways to use OO patterns to get this kind of functionality as well.

One thing I have yet to do now is write a UI to return control to if one chooses not to enter the password and username. I've been thinking of writing the front-end with Java, so I may check out Jython or something.

Because I'm far, far away from being an expert on login forms (just from what I come across while scanning SO and other blogs), feel free to make suggestions in the comments!

Monday, January 9, 2017

BST Implementation in Python

I've been going through John Washam's Google interview repo on GitHub and checking off concepts that I feel confident about. Because I don't use binary trees (BTs) in my code that often, I've felt that I need to brush up on them.

I wrote the following little implementation of the data structure in Python. While I'm more than comfortable with recursion, it's the base and edge-cases that can be tricky at times. For instance, when I was working with discrete convolution algorithms, recursively solving for the ranges over which to spatially iterate an image with each core in my laptop was more difficult to write than the convolution algorithm, and what I have there still isn't an optimal solution (e.g. what if the number of cores isn't a power of two?). [I think I'll attempt that again in the future.]

I'm still not positive I've weeded out all the errors. I'm writing unit tests though, and if I find any, I'll update it. I've written a bunch of unit tests with unittest, and I'm pretty sure that this is more correct.

EDIT (3/17): I was just reading the source of typing and found that Optional[<some type>] can be used as a shorthand for Union[<some type>, None] (where None is replaced by type(None).
#! /usr/bin/env python3.4
# -*- coding: utf-8 -*-

""" A binary tree implementation to store data. I like splitting the BT data
structure into two classes: one for the nodes, and one for the actual BT.

from typing import Union, Tuple, Optional

__all__ = ['BT']

class Node:
    """ A node type for the BT """

    def __init__(self, value: Optional[int], lvalue: Optional[int] =None,
                 rvalue: Optional[int] =None) -> None:
        self.value = value

        if lvalue:
            # lvalue != None
            self.lvalue = Node(lvalue)
            self.lvalue = None

        if rvalue:
            # rvalue != None
            self.rvalue = Node(rvalue)
            self.rvalue = None

    def get_value(self) -> Optional[int]:
        return self.value

    def get_l(self) -> Optional['Node']:
        """ Get the actual _object_ node """
        return self.lvalue

    def get_r(self) -> Optional['Node']:
        """ Again, get the actual node """
        return self.rvalue

    def get_lvalue(self) -> Optional['Node']:
        """ Every node points to another node or None """
        if self.lvalue:
            return self.lvalue.get_value()
            return None

    def get_rvalue(self) -> Optional['Node']:
        """ Again, every node points to another node or None """
        if self.rvalue:
            return self.rvalue.get_value()
            return None

    def set_lvalue(self, val: Union[int, 'Node', None]) -> None:
        """ Set the left child of the current node to a value """
        if self.has_lvalue():
            # Update what it points to
            raise ValueError('** Cannot update at the node level if already set')
            self.lvalue = Node(val) if type(val) is int or type(val) is None \
                                    else val

    def set_rvalue(self, val: Union[int, 'Node', None]) -> None:
        """ Set the right child of the current node to a value """
        if self.has_rvalue():
            # Update it
            raise ValueError('** Cannot update at the node level if already set')
            self.rvalue = Node(val) if type(val) is int or type(val) is None \
                                    else val

    # If you'd like to check if it points to an actual node and not None:

    def has_lvalue(self) -> bool:
        return self.lvalue is not None

    def has_rvalue(self) -> bool:
        return self.rvalue is not None

class BT:
    """ A binary tree structure. """

    def __init__(self, root: int) -> None:
        self.root = Node(root)  # (association relationship)
        self._size = 1

    def get_root_value(self) -> Optional[int]:
        return self.root.get_value()

    def get_size(self) -> int:
        return self._size

    def insert_iteratively(self, i: int) -> None:
        """ Creates a new node in the BT """
        current_node = self.root # != None

        while True:
            # This will terminate for any finite tree
            if i <= current_node.get_value():
                if current_node.has_lvalue():
                    current_node = current_node.get_l()
                    self._size += 1
                if current_node.has_rvalue():
                    current_node = current_node.get_r()
                    self._size += 1

    def insert_recursively(self, i: int, parent: Optional[Node] =None) -> None:
        """ Insert a value in the BT recursively """
        if not parent:
            parent = self.root

        if i <= parent.get_value():
            if parent.has_lvalue():
                self.insert_recursively(i, parent.get_l())
                self._size += 1
            if parent.has_rvalue():
                self.insert_recursively(i, parent.get_r())
                self._size += 1

    def lookup_from_node(self, i: int, n: Node) \
            -> Union[Tuple[Node, None], Tuple[Node, Node], Tuple[None, Node]]:
        """ Make it easier to look up a value starting at some node """
        return self.lookup(i, n)

    def lookup(self, i: int, n: Optional[Node] =None, parent: Optional[Node] =None) \
            -> Union[Tuple[Node, None], Tuple[Node, Node], Tuple[None, Node]]:
        """ Return the instance of Node that contains a value """
        if n is None:
            n = self.root   # self.root cannot be None and has no parent
            parent = None

        nval = n.get_value()

        if i < nval:
            if n.has_lvalue():
                return self.lookup(i, n.get_l(), n)
                return None, parent
        elif i > nval:
            if n.has_rvalue():
                return self.lookup(i, n.get_r(), n)
                return None, parent
            return n, parent
I also learned about type forward referencing by writing this script. You can read more about it in PEP 484, which introduces type hints. For example, if you try the following class without quotes around the return type 'Node', you get a NameError suggesting that the class A hasn't been declared yet (I wrote this while I was trying to figure out why it wouldn't work in the Node class above, which is why they look similar).
from typing import Union

class Node:
    def __init__(self, value: int, other: Union[int, None] =None) -> None:
        self.value = value
        self.l = Node(other) if type(other) is int else other

    def get_l(self) -> 'Node':
        return self.l

if __name__ == '__main__':
    X = Node(15, 16)
However, if you write them as string literals, i.e. 'A', then the type will be resolved later. This is nicely implemented in PyCharm as well.

What's more, I think it'd be fun to write a generalized BT. For example, a class that accepts any type and a function/operator for comparing two objects (for objects of type int we have <, >, and ==); or, given that the submitted type has rich comparison methods defined, I don't think it'd be necessary to submit a function as the way they interact with one another is thus defined by the objects in the binary tree.

Altogether, it's an interesting concept, and Python allows you to be very expressive in what you're trying to convey, both to the machine and others.