Skip to content
jbrownsonPublic

About

Puri's incremental UI in Lean 4, with its laws proved

Resources

Stars

1 star

Watchers

0 watching

Forks

Repository files navigation

lean-puri

Puri's change structures in Lean, with proved derivatives, and a window drawn by ThorVG. The example is a long scrolling list whose drawing is kept up to date from the list's edits and the scroll, instead of being laid out and drawn again each frame.

What's where

  • Puri/Change.lean: edit and change structures, Inc, Inc.ok, lift, whole, recompute.
  • Puri/List.lean: list edits, patch, diff, dmap, with proofs.
  • Puri/Drawing.lean: drawings (rows placed at heights) and their edits: translate, shift, insert, delete, update. diff makes them a change structure.
  • Puri/Scroll.lean: a list held split at the first row that shows, its edits (list edits and scrolling), and two outputs, each an Inc with its law: view (the drawing of the rows that show, view_ok) and extent (offset and height, for the scroll bar, extent_ok). The laws are at the end of the file. draw_eq says what the view is in terms of the whole list.
  • Puri/Axioms.lean: #guard_msgs checks of every law's axioms, so lake build fails on a sorry or a new axiom.
  • Puri/Platform.lean, native/platform.c: the SDL3 window, an offscreen target with no display, and Rows, retained rows whose operations are a drawing's edits.
  • Puri/Render.lean: makes a drawing's edits to Rows.
  • Example.lean: the 10,000-item list both programs use.
  • Demo.lean: the window. Bench.lean: the measurements.

Building

lake build

That checks the proofs and builds demo and bench. It needs:

  • SDL3 3.2 or later from the system's package manager, with its development files, found with pkg-config. On Arch: sdl3.
  • To build ThorVG: git, Meson, Ninja and a C++ compiler. ThorVG itself isn't installed; lake build fetches the pinned release (1.1.3) and builds it into .lake/build/thorvg, once. Few distributions package a recent ThorVG (most have 1.0.6, and Arch only the AUR's), and how fast it draws text is what the benchmark measures.

Lean comes from elan, at the version in lean-toolchain. The first build takes under a minute; after that, only what changed is rebuilt. If SDL3 is missing, lake build says so.

The demo

Run it from the repository's root, so it finds the font:

.lake/build/bin/demo
  • Wheel, arrow keys, Page Up/Down, Home/End: scroll.
  • Click an item: open or close it. The items below it shift.
  • Return or n: insert an item below the one under the pointer.
  • Delete, Backspace or d: delete the item under the pointer.
  • w: draw the whole window every frame instead, to compare.
  • a: scroll by itself, to watch and time frames.
  • q or Escape: quit.

Once a second, the title bar and standard output report the CPU work per frame: from the events to the frame being ready, not counting the wait for the display.

Measuring

scripts/bench.sh

That checks both paths agree, frame by frame, then times 5 rounds of 600 frames through each. It needs no display. scripts/bench.sh --callgrind also counts instructions per frame with valgrind, which is slow. .lake/build/bin/bench --sdl also checks the window code with SDL's offscreen video driver. --scale 1 measures at one pixel per point.

Results

On a 4-core cloud VM (Intel Xeon at 2.8 GHz), 2026-11-02: one script of 600 frames (scrolling at 4 to 22 points a frame, then up, a page, a jump to the top, a fling at 60, and an open, insert and delete every 40 frames), 5 rounds, a 520 × 760-point window of 10,000 items. Cloud timings are noisy, so the maxima mean little; the instruction counts (callgrind, 200 frames) don't vary.

Milliseconds per frame, median (90th percentile), at 2 pixels per point:

all frames scrolling jumps edits
whole window 17.3 (20.8) 17.3 (20.9) 15.7 17.3 (20.8)
incremental, less composite 0.27 (1.87) 0.011 (1.68) 16.0 0.96 (4.35)
incremental: composite alone (CPU here) 1.07 (1.75) 1.05 (1.69) 2.1 1.37 (2.06)
of which Lean (view.df, extent.df, apply) 0.005 (0.009) 0.005 (0.008) 0.014 0.010 (0.013)

Instructions per frame, median (90th percentile), at 2 pixels per point:

scrolling jumps edits
whole window 79.1M (85.2M) 79.1M 77.8M (86.9M)
of which Lean (apply, draw, extent) 1.29M 1.30M 1.29M
incremental: Lean 8.0K (8.7K) 18.7K 12.8K (14.9K)
incremental: render edits 1.7K (7.8M) 79.9M 8.2M (23.9M)
incremental: CPU composite 4.6M 4.6M 4.6M

At 1 pixel per point, drawing the whole window takes 7.3 ms (median) and the incremental path 0.09 ms less composite, 0.31 ms with it.

The derivatives cost microseconds. What costs is drawing text: ThorVG takes about 1.2 ms per row at 2 pixels per point (0.5 ms at 1), and the incremental path still draws each row that enters (0.66 per frame here). A jump draws every row, as drawing the whole window does. On a window, the composite is GPU work; offscreen, the CPU copies about 6 MB per frame, timed apart above.

The check compares every frame of the two paths: drawings, extents and the retained rows' tops are equal, and pixels differ by at most 17/255 (text antialiasing). At a fractional scale such as 1.5, rows are placed at whole pixels, so they can sit half a pixel from where drawing the whole window puts them.

About

Puri's incremental UI in Lean 4, with its laws proved

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages