Comment by UncleEntity

Been working on the design of an optimizer for my APL VM and asked Claude how this would fit in (as we don't have Dyalog extensions):

  The pattern is:

  f⌿ X ∘.g Y                                                                                                            
                                                                                                                        
  Where f is an associative reduction and g is a comparison. iBurg could recognize this tree shape and apply rewrites based on operator properties:                                                                                         
  ┌─────────┬───────────────────────────────────┐                                                                       
  │ Pattern │           Optimization            │                                                                       
  ├─────────┼───────────────────────────────────┤                                                                       
  │ +⌿X∘.≤Y │ Binary search count (if X sorted) │                                                                       
  ├─────────┼───────────────────────────────────┤                                                                       
  │ +⌿X∘.=Y │ Histogram / count matches         │                                                                       
  ├─────────┼───────────────────────────────────┤                                                                       
  │ ∨⌿X∘.=Y │ Membership (hash lookup)          │                                                                       
  ├─────────┼───────────────────────────────────┤                                                                       
  │ ∧⌿X∘.<Y │ All-less-than (single comparison) │                                                                       
  └─────────┴───────────────────────────────────┘                                                                       
  The generic rules would be:                                                                                                                              
  1. Shape rule: f⌿X∘.gY avoids materializing n×m matrix if f and g have algebraic properties that allow streaming/early-exit                                                                                                  
  2. Sortedness rule: If X is sorted and g is monotonic (≤, <, ≥, >), use binary search                                 
  3. Associativity rule: If f is associative (+, ∨, ∧, ⌈, ⌊), can process in chunks or parallel
  
  The cost model decides when O(n log m) binary search beats O(n×m) outer product -typically when both n and m exceed some threshold.                                                                                                       

iBurg is the Bottom-Up Rewrite System (BURS) based optimizer to operate over the continuation graphs the parser spits out, not sure where the 'i' part came from though...