tricu

An interpreted language for exploring Tree Calculus
Log | Files | Refs | README | LICENSE

b5971fc8616ce451c4c1bdc0b057635f63149da6df5dc49a07ed2b8570b10435.tri (3080B)

      1 !import prelude *
      2 !export *
      3 
      4 -- Small, source-independent dependency graph. Each entry is
      5 -- pair nodeName dependencyNames. All names must exist and be unique before
      6 -- graphSort; frontend validation owns missing/duplicate-name diagnostics.
      7 graphFind_ self entries name =
      8   lazyList
      9     (_ : nothing)
     10     (entry rest :
     11       lazyBool
     12         (_ : just entry)
     13         (_ : self rest name)
     14         (equal? (fst entry) name))
     15     entries
     16 
     17 graphFind = (entries name : y graphFind_ entries name)
     18 
     19 graphContains_ self names name =
     20   lazyList
     21     (_ : false)
     22     (item rest :
     23       lazyBool (_ : true) (_ : self rest name) (equal? item name))
     24     names
     25 
     26 graphContains = (names name : y graphContains_ names name)
     27 
     28 graphReady_ self dependencies available =
     29   lazyList
     30     (_ : true)
     31     (dependency rest :
     32       lazyBool
     33         (_ : self rest available)
     34         (_ : false)
     35         (graphContains available dependency))
     36     dependencies
     37 
     38 graphReady = (dependencies available : y graphReady_ dependencies available)
     39 
     40 graphFirstReady_ self entries available =
     41   lazyList
     42     (_ : nothing)
     43     (entry rest :
     44       lazyBool
     45         (_ : just entry)
     46         (_ : self rest available)
     47         (graphReady (snd entry) available))
     48     entries
     49 
     50 graphFirstReady = (entries available : y graphFirstReady_ entries available)
     51 
     52 graphRemove_ self entries name =
     53   lazyList
     54     (_ : t)
     55     (entry rest :
     56       lazyBool
     57         (_ : rest)
     58         (_ : pair entry (self rest name))
     59         (equal? (fst entry) name))
     60     entries
     61 
     62 graphRemove = (entries name : y graphRemove_ entries name)
     63 
     64 -- Once no node is ready, every pending node has a pending dependency. Follow
     65 -- those edges until a name repeats; the repeated name is a genuine cycle
     66 -- witness, even if the initial pending entry only leads into the cycle.
     67 graphFirstPending_ self dependencies entries =
     68   lazyList
     69     (_ : nothing)
     70     (name rest :
     71       lazyMaybe
     72         (_ : self rest entries)
     73         (entry : just name)
     74         (graphFind entries name))
     75     dependencies
     76 
     77 graphFirstPending = (dependencies entries :
     78   y graphFirstPending_ dependencies entries)
     79 
     80 graphCycle_ self current entries seen =
     81   lazyBool
     82     (_ : current)
     83     (_ : lazyMaybe
     84       (_ : current)
     85       (entry : lazyMaybe
     86         (_ : current)
     87         (name : self name entries (pair current seen))
     88         (graphFirstPending (snd entry) entries))
     89       (graphFind entries current))
     90     (graphContains seen current)
     91 
     92 graphCycle = (current entries : y graphCycle_ current entries t)
     93 
     94 -- Result [name] cycleName; ties preserve input order among simultaneously
     95 -- ready nodes. On a cycle the result's error payload is a witness name.
     96 graphSort_ self entries available reversed =
     97   lazyList
     98     (_ : ok (reverse reversed) t)
     99     (entry rest :
    100       lazyMaybe
    101         (_ : err (graphCycle (fst entry) entries) t)
    102         (ready : self (graphRemove entries (fst ready))
    103                    (pair (fst ready) available)
    104                    (pair (fst ready) reversed))
    105         (graphFirstReady entries available))
    106     entries
    107 
    108 graphSort = (entries : y graphSort_ entries t t)
    109