graph.hl.rkt (3835B)
1 #lang hyper-literate typed/racket/base #:no-auto-require 2 @(require scribble-math 3 racket/require 4 scribble-enhanced/doc 5 racket/require 6 hyper-literate 7 (subtract-in scribble/struct scribble-enhanced/doc) 8 scribble/decode 9 (for-label racket/format 10 racket/promise 11 racket/list 12 type-expander 13 (except-in (subtract-in typed/racket/base type-expander) 14 values) 15 (only-in racket/base values) 16 (subtract-in racket/contract typed/racket/base) 17 phc-toolkit 18 phc-toolkit/untyped-only 19 remember)) 20 @(unless-preexpanding 21 (require (for-label (submod "..")))) 22 @doc-lib-setup 23 24 @title[#:style (with-html5 manual-doc-style) 25 #:tag "graph-impl" 26 #:tag-prefix "phc-graph/graph-impl"]{Implementation of the graph macro} 27 28 @(chunks-toc-prefix 29 '("(lib phc-graph/scribblings/phc-graph-implementation.scrbl)" 30 "phc-graph/graph-impl")) 31 32 33 @chunk[<graph> 34 (define-syntax define-graph 35 (syntax-parser 36 [<signature> 37 <implementation>]))] 38 39 @chunk[<signature> 40 (_ _name 41 [[_nodeᵢ [_fieldᵢⱼ :colon _τᵢⱼ] …] …] 42 [[(_mappingₖ [_argₖₗ _τₖₗ] …) :colon _return-typeₖ . _bodyₖ] …])] 43 44 @chunk[<implementation> 45 #'()] 46 47 @section{Overview of the implementation (draft)} 48 49 @chunk[<implementation-draft> 50 <create-Qₖ> 51 <re-bind-mappings> 52 <define-indices> 53 <process-queues>] 54 55 @chunk[<define-indices> 56 (define/with-syntax (_indexₖ …) (stx-map gensym #'(_idxₖ …))) 57 #'(begin 58 (define-type _indexₖ (graph-index '_indexₖ)) 59 …)] 60 61 @chunk[<define-index> 62 (struct (K) graph-index ([key : K] [index : Index]))] 63 64 Create one queue @racket[_Qₖ] for each mapping: 65 66 @chunk[<create-Qₖ> 67 #'(begin 68 (define _Qₖ <create-queue>) 69 (define _Qₖ-enqueue <TODO>) 70 (define _Qₖ-pop <TODO>) 71 …)] 72 73 Re-bind mappings to catch outbound calls: 74 75 @chunk[<re-bind-mappings> 76 #'(let ([_mappingₖ _make-placeholderₖ] …) 77 . bodyₖ)] 78 79 Define functions which enqueue into a given @racket[_Qₖ] and start processing. 80 The final @racket[_name] macro dispatches to these functions. 81 82 @chunk[<entry-pointₖ> 83 #'(begin 84 (define (_entry-pointₖ _argₖₗ …) 85 (entry-point #:mappingₖ (list (list _argₖₗ …)))) 86 …)] 87 88 These are based upon the main @racket[entry-point], which takes any number of 89 initial elements to enqueue, and processes the queues till they are all empty. 90 91 @chunk[<entry-point> 92 #'(define (entry-point #:mappingₖ [_argsₖ* : (Listof (List τₖₗ …)) '()]) 93 (for ([_argsₖ (in-list _argsₖ*)]) 94 (let-values ([(_argₖₗ …) _argsₖ]) 95 (Qₖ-enqueue _argₖₗ …))))] 96 97 @chunk[<process-queues> 98 (until queues are all empty 99 process item, see below)] 100 101 @itemlist[ 102 @item{Find and replace references to old nodes and new incomplete nodes and 103 new placeholder nodes, instead insert indices.} 104 @item{Problem: we need to actually insert indices for references to nodes, 105 not for references to mappings (those have to be inlined).}] 106 107 108 @chunk[<*> 109 (require racket/require 110 (for-syntax (subtract-in racket/base 111 subtemplate/override) 112 phc-toolkit/untyped 113 type-expander/expander 114 subtemplate/override) 115 "traversal.hl.rkt" 116 phc-toolkit) 117 <define-index> 118 <graph>]