My name is Jared Clarke.

Tools:

• Pratt Parser
• Document Object Model (DOM)

Project:

December 2021, I resolved to teach myself how to program. This calculator — which I built with plain HTML, CSS, and JavaScript — was the culmination of careful study. September 2023, I rewrote this application to better reflect my improving skillset.

Both calculators are built on top of expression parsers. My first parser was rudimentary — easily misled by unexpected character combinations and misplaced whitespace. Anticipating malformed user input is complex, and I had shifted much of this complexity over to a tangle of regular expressions, which were cryptic and hard to debug. These too would fail.

My new calculator's core is a top-down operator precedence parser modeled on ideas pioneered by the computer scientist Vaughan R. Pratt. A full-featured parser, it handles infix and prefix notation, left and right associativity, nested and mismatched parenthetical groupings, multiple levels of precedence and all types of whitespace. Errors are made explicit through robust error handling and a formatted user interface.

A version of this calculator application, complete with extensive inline documentation, can be found on Github.

Notes:

Top-down operator precedence parsing, as imagined by Vaughan Pratt, combines lexical semantics with functions. Each lexeme is assigned a function — its semantic code. To parse a string of lexemes is to execute the semantic code of each lexeme in turn from left to right.

There are two types of semantic code:

1. nud: a lexeme function without a left expression — null denotation.
2. led: a lexeme function with a left expression — left denotation.

The engine of Pratt's technique, parse_expression drives the parser, calling the semantic code of each lexeme in turn from left to right. For every level of precedence — dictated by position and binding power — there is a call to parse_expression either through the nud or led parser of the associated lexeme. The resolution of parse_expression is to return either an evaluated expression or an error token.

function parse_expression(rbp) {
    const token = state.next();
    const [nud, ok] = table.get_parser(token.type, "nud");
    if (!ok) {
        token.message += constants.NOT_PREFIX;
        return [null, token];
    }
    let [x, error] = nud(token);
    if (error !== null) {
        return [null, error];
    }
    while (rbp < table.get_binding(state.peek())) {
        const token = state.next();
        const [led, ok] = table.get_parser(token.type, "led");
        if (!ok) {
            token.message += constants.NOT_INFIX;
            return [null, token];
        }
        [x, error] = led(x, token);
        if (error !== null) {
            return [null, error];
        }
    }
    return [x, null];
}

Parallax Animation

Tools:

• CSS animations
• CSS perspective
• CSS grid
• Intersection Observer API

Project

Summer 2022, I discovered a short film about the Walt Disney Company's pioneering work with the multi-plane camera — a device used to create parallax backgrounds in animated films. I was inspired to recreate this technology in CSS and JavaScript.

I painted a mountain landscape in my raster editor and then saved its four layers to separate image files. I saved the three foreground layers — one tree layer and two hill layers — to PNGs to preserve transparency. I saved the opaque background image, Mount Rainier, to a JPEG. Noisy images, like digital paintings, compress better as lossy images.

I used grid-template-areas in CSS grid to layer my images, and I used CSS perspective to insert a z-index of 50 pixels within their containing element. I applied CSS animations to move my layers independently through this 50-pixel space. The movement of layers at different speeds creates the illusion of depth — just like a multi-plane camera.

Notes:

I attached an Intersection Observer to my animation. If the user either forgets or chooses not to turn off the animation before scrolling to the next section in my portfolio, the observer will switch it off for them. Although CSS animations usually run on a separate thread, I don't want to waste any browser resources.

Cursor

Tools:

• Scheme (R6RS)
• Chez Scheme Compiler
• Parsing Expression Grammars, Bryan Ford
• A Parsing Machine for PEGs, Roberto Ierusalimschy and Sérgio Medeiros

Background:

I like regular expressions. I dislike regular expression patterns. Invented by Stephen Kleene, regular expressions are a mathematical formalism for describing sequences of symbols via three operations: alternation (|), concatenation (•), and repetition (*).

Regular expressions proved a simple and effective basis for early text-matching tools like AWK and GREP. The interfaces to these tools were regular expression patterns, strings of text interspersed with alternation and repetition operators. Character sequences implied concatenation.

;; === Perl-like Regular Expression ===
;; number = /[+-]?\d+(?:\.\d+)?(?:[eE][+-]?\d+)?/

;; === Cursor: PEG Alternative ===
(define number
  (let* ([digits   (repeat+1 (one-of "0123456789"))]
         [sign     (maybe (or-else (char #\-) (char #\+)))]
         [whole    (or-else (char #\0) digits)]
         [integer  (and-then sign whole)]
         [fraction (maybe (and-then (char #\.) digits))]
         [exponent (maybe (and-then (or-else (char #\e)
                                             (char #\E))
                                     sign
                                     digits))])
    (and-then integer fraction exponent)))

At some point, however, regular expressions stopped being simple. Programmers wanted more from their tools. Features were added. Terseness became a liability as new operations cluttered regular expression strings.

Semantics too became complicated. Regular expressions are intentionally limited. A simple set of inductive properties provide strong guarantees of computational time and space. Adding features, like backtracking, destroy these formal properties.

I wanted something simpler and capable of recognizing larger classes of patterns. I read about alternative formalisms and their lesser-known libraries. I subsequently discovered LPeg, a pattern matching library based on Parsing Expression Grammars (PEG). LPeg has a heavily-documented and clean architecture. I leapt at the opportunity to build my own library using that architecture as a blueprint.

Project:

I built my PEG library, Cursor, using the Scheme programming language as implemented by the Chez Scheme compiler. The API is a small set of PEG operators converted to s-expressions. My source code — with extended examples, documentation, and attribution — can be found on Github.

Each operator is either a function or variable that returns an immutable and persistent syntax tree, a tree that describes a PEG pattern. These trees, like PEG expressions, are composable. Any number of syntax trees can be combined into any number of larger syntax trees. At any time — although usually at a module boundary — a syntax tree can be passed to compile, a function that returns a function. This function is a closure over a compiled list of instructions and a reference to the Cursor virtual machine. The machine runs said instructions over strings provided by the caller of its containing closure.

;; === syntax trees ===
(define A (char #\A))
(define B (char #\B))
(define C (char #\C))

;; === composition ===
(define A-B-and-C (and-then A B C))
(define A-B-or-C  (or-else A B C))

;; === pattern matchers ===
(define A-B-and-C? (compile A-B-and-C))
(define A-B-or-C?  (compile A-B-or-C))

The full power of Parsing Expression Grammars is realized in Cursor's grammar form. grammar allows the definition of mutually-defined and recursive patterns. Context-free grammars and some non-context-free grammars are recognizable by this form. Unlike regular expressions, parsing expression grammars can build parsers.

(define nested
  (grammar
    [X (and-then (char #\()
                 (or-else (rule X) empty)
                 (char #\))))]))

(define nested? (compile nested))

(nested? "(((())))") ;; -> #t
(nested? "(()")      ;; -> #f

The heart of Cursor is its virtual machine. I modeled Cursor after the virtual machine in LPeg, a pattern-matching library implemented in C for the Lua programming language. The machine and library were created by Roberto Ierusalimschy and Sérgio Medeiros.

(define run-vm
   (lambda (text program)
      (let ([size (vector-length text)])
        (letrec ([state
                 (lambda (ip sp stack captures)
                   (let ([code (vector-ref program ip)])
                     (cond
                      ;; [(char? x), text[sp] = x]
                      ;; (ip, sp, stack, captures) -> (ip+1, sp+1, stack, captures)
                      ;;
                      ;; [(char? x), text[sp] ≠ x]
                      ;; (ip, sp, stack, captures) -> (fail, sp, stack, captures)
                      [(char? code)
                       (if (and (< sp size)
                                (char=? code (vector-ref text sp)))
                           (state (+ ip 1)
                                  (+ sp 1)
                                  stack
                                  captures)
                           (fail-state ip sp stack captures))]
                   ; === code omitted ===
                   )]
                 [fail-state
                  (lambda (ip sp stack captures)
                    ; === code omitted ===
                    )])
           (#| === code omitted === |#)))))

The machine is essentially a four tuple: (ip, sp, stack, captures). ip tracks the machine's position in the instruction list. sp tracks the machine's position in the input string. stack tracks pending return addresses of non-terminals and alternative instructions. captures tracks capture offsets within the input string and the instructions associated with those captures.

Whereas LPeg's virtual machine — its tuple — is implicit in its for loops and labeled goto statements, Cursor's virtual machine is explicit. Because Scheme has proper tail calls, Cursor is able to pass its tuple — its continuation — between mutually-defined functions (state ip sp stack captures) and (fail-state ip sp stack captures). Cursor's full virtual machine and documentation can be found on GitHub.

Luka.js

// Produces unary functions.
function unary(operation) {
    return Object.freeze(function (x) {
        return operation(x);
    });
}

// Produces binary functions.
function binary(operation) {
    return Object.freeze(function (x, y) {
        return operation(x, y);
    });
}

// Produces functions that fold a set into a summary value.
function foldable(operation) {
    return Object.freeze(function (...xs) {
        return xs.reduce(
            (total, x) => operation(total, x),
        );
    });
}

// "op" acts as namespace for arithmetic functions.
// Its null prototype prevents namespace pollution
// from inherited objects.
const op = Object.create(null);

// Unary Operations
op.neg = unary((x) => 0 - x);

// Binary Operations
op.add = foldable((x, y) => x + y);
op.sub = foldable((x, y) => x - y);
op.mul = foldable((x, y) => x * y);
op.div = foldable((x, y) => x / y);
op.exp = binary((x, y) => Math.pow(x, y));
op.rem = binary((x, y) => x % y);

// Make exported namespace immutable.
export default Object.freeze(op);

Tools:

• Array.prototype.reduce()
• Object.create()
• Object.freeze()

Project:

A binary operation is a rule combining two elements of a set to create a third. In arithmetic the most common way to represent binary operations is infix notation, where the operator sits between its two operands. But infix notation is ambiguous. It's unclear whether 1 + 2 * 3 evaluates (1 + 2) * 3 or 1 + (2 * 3), so mathematicians use a set of conventions, the order of operations, to resolve this confusion.

The order of operations, however, is no fixed thing. It's unclear whether unary negation precedes exponentiation, whether implied multiplication precedes explicit division. Almost every programming language has their own precedence table. Each is subtly — or drastically — different from the other.

I created the JavaScript library Luka.js to sidestep this confusion over binary operations. Luka.js provides functional replacements for a handful of arithmetic operators: [+, -, *, /, **, %]. Unlike its operators, JavaScript functions are straightforward. They are parenthesized and strictly applied, meaning they evaluate inward to outward precisely when they are called. The ambiguous 1 + 2 * 3 becomes the explicit add(1, mul(2, 3)). Also: JavaScript functions can have variable arity. While + can input only two arguments, add can input 1 through n arguments.

Notes:

• The entire Luka.js API is contained within a null-inheriting, immutable object literal. The object keeps the API simple. All functions are kept within a single, unchangeable namespace. No pollution from the prototypal chain can obscure them.

• JavaScript functions are also objects. By default, properties — even other functions — can be attached to a function object at anytime during the life of a program, potentially changing its output. My unary, binary, and foldable factory functions produce immutable function objects to prevent this behavior from altering my API.