soma.cell

Family tree: Person records with a list of children records, walked recursively

Demonstrates a multi-way tree of records, recursive counting, and collecting a generation by depth.

A Soma program from the records part of the verified corpus: 71 lines, cells FamilyTree, FamilyTreeTest. It passes soma check with soma 3.2.4.

How it is built

The cell FamilyTree declares 4 signals in its face: root() -> Map, size() -> Int, max_depth() -> Int and names_at(depth: Int) -> List. Handlers: root (line 13), size (line 23), max_depth (line 35) and names_at (line 48). Private helpers: _count, _depth and _collect.

The file also holds 1 test cell (FamilyTreeTest) with 5 assertions, run by soma test.

Generated from soma describe on this file.

The source

family_tree.cell

// Family tree: Person records with a list of `children` records, walked
// recursively. Demonstrates a multi-way tree of records, recursive counting,
// and collecting a generation by depth.

cell FamilyTree {
    face {
        signal root() -> Map
        signal size() -> Int
        signal max_depth() -> Int
        signal names_at(depth: Int) -> List
    }

    on root() {
        return Person { name: "Grandma", children: list(
            Person { name: "Mom", children: list(
                Person { name: "Me",  children: list() },
                Person { name: "Sis", children: list() }) },
            Person { name: "Uncle", children: list(
                Person { name: "Cousin", children: list() }) }
        )}
    }

    on size() {
        return _count(root())
    }

    on _count(p: Map) {
        let total = 1
        for c in p.children {
            total = total + _count(c)
        }
        return total
    }

    on max_depth() {
        return _depth(root())
    }

    on _depth(p: Map) {
        if len(p.children) == 0 { return 1 }
        let best = 0
        for c in p.children {
            best = max(best, _depth(c))
        }
        return 1 + best
    }

    on names_at(depth: Int) {
        return _collect(root(), 0, depth)
    }

    on _collect(p: Map, cur: Int, target: Int) {
        if cur == target { return list(p.name) }
        let out = list()
        for c in p.children {
            out = list(out, _collect(c, cur + 1, target)) |> flatten()
        }
        return out
    }
}

cell test FamilyTreeTest {
    rules {
        assert size() == 6
        assert max_depth() == 3
        assert names_at(0)[0] == "Grandma"
        assert len(names_at(1)) == 2
        assert len(names_at(2)) == 3
    }
}

What the toolchain says

Run on a fresh copy of the program at build time; the outputs are pasted unedited.

$ soma check family_tree.cell
✓ All checks passed.
$ soma test family_tree.cell
test FamilyTreeTest ...
  ✓ assert size() == 6
  ✓ assert max_depth() == 3
  ✓ assert names_at(0)[0] == "Grandma"
  ✓ assert len(names_at(1)) == 2
  ✓ assert len(names_at(2)) == 3

5 tests: 5 passed, 0 failed
$ soma verify family_tree.cell
Verifying family_tree.cell...

FamilyTree/termination:

  ⚠ `size` calls `FamilyTree._count`, which may not terminate
  ⚠ handler `_count`: recursive call without provable decreasing argument
  ⚠ `max_depth` calls `FamilyTree._depth`, which may not terminate
  ⚠ handler `_depth`: recursive call without provable decreasing argument
  ⚠ `names_at` calls `FamilyTree._collect`, which may not terminate
  ⚠ handler `_collect`: recursive call without provable decreasing argument

0 passed, 6 warnings, 0 failures
Temporal: 0 passed, 0 failed
VERIFY OK

Builtins used

flatten, len, list, max

Source file: /corpus/records/family_tree.cell · examples/corpus/records/family_tree.cell