• Top
    • Documentation
    • Books
    • Recursion-and-induction
    • Boolean-reasoning
    • Projects
    • Debugging
    • Std
    • Proof-automation
    • Macro-libraries
    • ACL2
      • Theories
      • Rule-classes
      • Proof-builder
      • Hons-and-memoization
        • Memoize
        • Fast-alists
        • Hons
        • Set-max-mem
        • Hons-enabled
        • Unmemoize
        • Number-subtrees
        • Events
        • History
        • Parallelism
        • Programming
        • Start-here
        • Real
        • Debugging
        • Miscellaneous
        • Output-controls
        • Macros
        • Interfacing-tools
      • Interfacing-tools
      • Hardware-verification
      • Software-verification
      • Testing-utilities
      • Math
    • Hons-and-memoization
    • ACL2-built-ins

    Number-subtrees

    (number-subtrees x) returns the number of distinct subtrees of X, in the sense of equal

    In the logic, number-subtrees is defined as the length of cons-subtrees.

    Under the hood, we first hons-copy X to obtain a normed version, then count the number of unique conses in X using an EQ hash table.

    Function: number-subtrees

    (defun number-subtrees (x)
           (declare (xargs :guard t))
           (len (cons-subtrees x 'number-subtrees)))