Port more benchmarks from Racket

[bennn]

Try porting more benchmarks from Racket.

Two options for this:

• type a small chunk of each benchmark
• fully type, randomly sample

[bennn]

I started porting suffixtree, its taking longer than expected but this might work.

Will try to fnish tonight, then try to port another

[bennn]

Failure for now. The writing is a higher priority.

[bennn]

FWIW, here is a suffixtree function that Reticulated cannot type. All the code is below; key points:

• the comment at the top is from the original author (Danny Yoo, src)
• the problematic type signature starts at the first non-comment line below

;; node-follow/k: node label (node -> A)
;;                           (node number -> B)
;;                           (node label number -> C)
;;                           (node number label number -> D)
;;                    -> (union A B C D)
;; 
;; Traverses the node's edges along the elements of the input label.
;; Written in continuation-passing-style for leakage containment.
;; One of the four continuation arguments will be executed.
(: node-follow/k (All (A B C D)
                      (-> Node
                          Label
                          (-> Node A)
                          (-> Node Index B)
                          (-> Node Label Index C)
                          (-> Node Index Label Index D)
                          (U A B C D))))
(define (node-follow/k node
                       original-label
                       matched-at-node/k
                       matched-in-edge/k
                       mismatched-at-node/k
                       mismatched-in-edge/k)
  (: EDGE/k (-> Node Label Index (U A B C D)))
  (define (EDGE/k node label label-offset)
    (: up-label Label)
    (define up-label (node-up-label node))
    (let loop ((k 0))
      (define k+label-offset (+ k label-offset))
      (cond
       ((= k (label-length up-label))
        (unless (index? k+label-offset) (error "node/folllowd"))
        (NODE/k node label k+label-offset))
       ((= k+label-offset (label-length label))
        (unless (index? k) (error "node/followk"))
        (matched-in-edge/k node k))
       ((label-element-equal? (label-ref up-label k)
                              (label-ref label k+label-offset))
        (loop (add1 k)))
       (else
        (unless (and (index? k)
                     (index? k+label-offset)) (error "node-follow/k mismatched fail"))
        (mismatched-in-edge/k node k label
                              k+label-offset)))))
  (: NODE/k (-> Node Label Index (U A B C D)))
  (define (NODE/k node label label-offset)
    (if (= (label-length label) label-offset)
        (matched-at-node/k node)
        (let ([child (node-find-child node (label-ref label label-offset))])
          (if child
              (EDGE/k child label label-offset)
              (mismatched-at-node/k node label label-offset)))))
  (NODE/k node (label-copy original-label) 0))

[bennn]

More data, here's a table of racket benchmarks from the GTP repo and whether they use "All" types:

benchmark	at least one All-type ?
acquire	X
dungeon	X
forth
fsm	X
fsmoo
gregor
kcfa	X
lnm
mbta	X
morsecode	X
quadBG	X
quadMB	X
snake
suffixtree	X
synth	X
take5
tetris
zombie
zordoz	X

Time-permitting it would be good to explore the "small" benchmarks that don't use All-types.

(Comparing across languages is apples to oranges, so give these thoughts little/no weight: morsecode was fast in TR, will it be fast in Retic? snake and tetris had very high overhead in TR, I think because the types implied extra traversals of lists)

[bennn]

Alternatively ... put tag soundness in Typed Racket