2022 Swift 5.6 SwiftParsec Bow swift-collections swift-argument-parser

Blang (Bitis)

Lazy functional language with compile-time ownership and borrowing instead of garbage collection

Overview

Blang is a complete compiler and interpreter for a lazy functional programming language that replaces garbage collection with compile-time ownership and borrowing analysis -- the first language to combine Haskell-style lazy evaluation with Rust-style memory management. The compiler implements a full pipeline from source to interpreted execution: lexing, parsing, Hindley-Milner type inference with polymorphism, lifetime analysis, borrow checking with cycle detection, case lifting, three-pass optimization, and a stack-based virtual machine interpreter with runtime memory tracking. Published as MSc thesis at the University of Ljubljana.

Architecture

The pipeline is composed via a custom >>- (bind) operator on Either<Error, _>, forming a monadic chain where each phase transforms the AST and can short-circuit on error. Semantic analysis phases run twice -- once before case lifting and once after -- because case lifting transforms multi-equation function definitions into single-case expressions, changing the AST shape. Each major phase has its own monad stack (StateT<Either<Error>, PhaseState, _>) with automatic backtrace threading at every AST node visit.

Key Concepts

Self-Borrows

The central novelty of the thesis. In a lazy language, a value can contain a reference to itself because the thunk hasn't evaluated yet -- enabling cyclic structures (graphs, infinite streams) without violating ownership rules. The compiler detects self-borrows by comparing the borrow lifetime with the binding lifetime.

Lifetime Prefix Trees

Lifetimes are modeled as hierarchical string identifiers where parent-child relationships are prefix queries on strings. Lifetime 'aa is parent of 'aab because "aab".hasPrefix("aa"). This turns tree operations into O(n) string operations -- entering a scope appends a character, exiting pops it.

Code Highlights

Self-Borrow Detection in Lifetime Analysis

let isSelfBorrow = lifetime == existingLifetime?.lifetime
let isValid = lifetime.isParent(of: currentLifetime) || isSelfBorrow

guard isValid else {
  return .error(.cannotReferenceLocalValue)
}

// If it's a self-borrow, remove the lifetime annotation from the body
// to prevent the borrow checker from treating it as an escaping reference
let body = isSelfBorrow ? body.withLifetime(nil) : body

Lifetime as Prefix Tree (Parent/Child via String Prefix)

extension LifetimeIdentifier: ParentChildRelation {
  public func isParent(of other: LifetimeIdentifier) -> Bool {
    self != other && other.identifier.hasPrefix(self.identifier)
  }

  public func isChild(of other: LifetimeIdentifier) -> Bool {
    self != other && self.identifier.hasPrefix(other.identifier)
  }

  public func commonParent(_ other: LifetimeIdentifier) -> LifetimeIdentifier? {
    let prefix = self.identifier.commonPrefix(with: other.identifier)
    if prefix.isEmpty { return nil }
    return .init(identifier: prefix)
  }
}

Monadic Pipeline Composition with Backtrace Threading

public func >>-<A: HasPosition, B>(
  _ m: StateT<EitherPartial<BCError>, BCState, A>,
  _ f: @escaping (A) -> StateT<EitherPartial<BCError>, BCState, B>
) -> StateT<EitherPartial<BCError>, BCState, B> {
  m
    .flatMap(BorrowCheckM<A>.backtrace)  // automatic backtrace
    .flatMap(f)^
}

Highlights

Novel PL contribution: first lazy functional language using ownership/borrowing instead of GC, introducing self-borrows for cyclic data structures (graphs, infinite streams)
Full-stack compiler pipeline in Swift (~65 source files): lexer, parser, Hindley-Milner type inference, lifetime analysis, borrow checking, case lifting, IR generation, three-pass optimizer, and stack-based VM
Lifetime prefix trees: hierarchical lifetimes as strings where parent-child queries reduce to string prefix operations
200+ test cases for memory analysis phases organized by error category, with a 700-line formal ownership manifesto
Research-grade monadic architecture: three independent monadic phases (TypecheckM, LifetimeAnalyseM, BorrowCheckM) with Haskell-style operators

Related Projects

Atheris

Complete compiler for a Swift-like OOP language with vtables and polymorphic dispatch

Java

Designed and implemented a complete compiler from scratch for a Swift-like OOP language (~120 Java source files, ~8,000+ lines)

SML-to-Racket

Source-to-source compiler with lambda calculus IR and Church-encoded algebraic datatypes

Swift

Dual-target compiler with direct Racket emission and a lambda calculus IR featuring Church-encoded booleans, tuples, and algebraic datatypes

PINS Compiler Course

8 progressive compiler assignments from lexer to interpreter for 100+ university students

Java

Designed a complete 8-assignment compiler course from lexical analysis to a working interpreter (12 to 73 source files incrementally)

Back to CV