egnha

A short note on tail-call elimination via exception handling

The basic mechanism of [tail-call elimination][tail-call-elimination] is simple: when a procedure reaches a tail call, capture the transformed arguments and feed them back into the machinery of the procedure. Tail calls are thereby made iteratively; they do not accumulate on the call stack.

There is a folklore trick to implement this mechanism using exception handling: in place of a tail call, raise an exception containing the transformed arguments, then catch the exception in order to pass the arguments to a new call. This isn't quite the same as feeding the arguments back into the machinery of the procedure, because a new call is made (with the concomitant overhead of a new environment, etc.). But the previous call is nevertheless popped from the call stack, and thereby eliminated. I could not trace the source of this trick, but it is surely ancient, cf. [Simmons–Beckman–Murphy][Simmons-Beckman-Murphy] (2010), [Norvig][Norvig] (1992, Sec. 22.3

egnha

from itertools import islice, tee

def pairs(xs):
    """a, b, c, d, ... -> (a, b), (c, d), ..."""
    fst, snd = (islice(_xs, start, None, 2) for start, _xs in enumerate(tee(xs)))
    return zip(fst, snd)

egnha

"""
Advent of Code 2019: Day 6, Part 1
"""

from collections import defaultdict

tree = defaultdict(list)

with open("06-input.txt") as f:
    for line in f.readlines():

egnha

Day 5

from typing import Callable as Fun, Dict, List, Tuple, Optional, NamedTuple
from itertools import accumulate, chain, dropwhile, islice, repeat
from operator import add, mul, eq, lt, getitem

Helper functions

egnha

Build Emacs on the Mac

emacs-mac by Mitsuharu Yamamoto enhances vanilla GNU Emacs by enabling various Safari-like conveniences, such as tabs and tab overview and back/forward swiping between buffers. It also enables various Mac-specific Elisp commands, such as (mac-auto-operator-composition-mode) to enable font ligatures.

You can install a pre-built binary with the Homebrew formula provided by railwaycat. But be aware that you can't launch it from Spotlight, because it doesn't install Emacs.app in /Applications (you'd have to do that manually).

Install dependencies

brew install autoconf gnutls pkg-config texinfo

egnha

Subpixel rendering on Ubuntu 18.04+

In /etc/environment, set

FREETYPE_PROPERTIES="truetype:interpreter-version=35 cff:no-stem-darkening=1 autofitter:warping=1"

See https://forum.ubuntuusers.de/topic/verdana-scharfe-schriften-sharp-fonts-with-ver/#post-8914328

egnha

Generalized Voronoi “tesselation”: variation on a theme (AoC 2018, Day 6)

The point of this vignette is to introduce a simple notion of a generalized Voronoi tesselation (in the context of Day 6), and to illustrate how they can be implemented succinctly with tensors.

Day 6, abstractly

A common procedure can be applied to solve both parts of the Day 6 puzzle:

egnha

`%?%` <- function(value, predicate) {
  list(value = value, predicate = predicate(value))
}

# Implicitly, `assert` is either a boolean or a value-predicate pair
`%because%` <- function(assert, reason) {
  if (is.logical(assert)) {
    if (!assert) stop(reason, call. = FALSE)
    return(invisible(TRUE))
  }

egnha

import Foundation

infix operator ^^

func ^^<A>(_ values: [A], _ exponent: Int) -> [[A]]? {
    guard exponent >= 0 else { return nil }
    func product(prod: [[A]], xs: [A]) -> [[A]] {
        return prod.flatMap { p in xs.map { x in p + [x] } }
    }
    let factors = [[A]](repeating: values, count: exponent)

egnha

// Jared Sinclair: https://twitter.com/jaredsinclair/status/951536021459619840

class NotificationObserver {
    private var observers = [NSObjectProtocol]()
    private let queue: OperationQueue
    
    init(queue: OperationQueue = .main) {
        self.queue = queue
    }