Open bennn opened 7 years ago
I started porting suffixtree, its taking longer than expected but this might work.
Will try to fnish tonight, then try to port another
Failure for now. The writing is a higher priority.
FWIW, here is a suffixtree
function that Reticulated cannot type. All the code is below; key points:
;; 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))
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)
Alternatively ... put tag soundness in Typed Racket
Try porting more benchmarks from Racket.
Two options for this: