commit 1f395775ce0466e164a0d71f65b5c060958a2b7a
parent f3ea5a492954c79fb3c555b836e512925884f2db
Author: Georges Dupéron <georges.duperon@gmail.com>
Date: Sun, 2 Oct 2016 23:48:49 +0200
Build the hyper-literate document.
Diffstat:
6 files changed, 176 insertions(+), 49 deletions(-)
diff --git a/.travis.yml b/.travis.yml
@@ -50,8 +50,10 @@ before_script:
# packages without it getting stuck on a confirmation prompt.
script:
- raco test -x -p phc-graph
+ - raco setup --check-pkg-deps --no-zo --no-launcher --no-install --no-post-install --no-docs --pkgs phc-graph
+ - raco pkg install --deps search-auto doc-coverage
+ - raco doc-coverage phc-graph
after_success:
- - raco setup --check-pkg-deps --pkgs phc-graph
- raco pkg install --deps search-auto cover cover-coveralls
- raco cover -b -f coveralls -d $TRAVIS_BUILD_DIR/coverage .
diff --git a/info.rkt b/info.rkt
@@ -6,9 +6,17 @@
"phc-adt"
"type-expander"
"hyper-literate"
- "scribble-enhanced"))
-(define build-deps '("scribble-lib" "racket-doc"))
-(define scribblings '(("scribblings/phc-graph.scrbl" ())))
+ "scribble-enhanced"
+ "typed-racket-lib"))
+(define build-deps '("scribble-lib"
+ "racket-doc"
+ "remember"
+ "typed-racket-doc"))
+(define scribblings
+ '(("scribblings/phc-graph.scrbl" ()
+ ("Data Structures"))
+ ("scribblings/phc-graph-implementation.scrbl" (multi-page)
+ ("Data Structures"))))
(define pkg-desc "Description Here")
(define version "0.0")
(define pkg-authors '("Georges Dupéron"))
diff --git a/scribblings/phc-graph-implementation.scrbl b/scribblings/phc-graph-implementation.scrbl
@@ -0,0 +1,14 @@
+#lang scribble/manual
+@require[@for-label[phc-graph
+ racket/base]]
+
+@title{Ph.C Graph library: Implementation}
+@author[@author+email["Georges Dupéron" "georges.duperon@gmail.com"]]
+
+This library is implemented using literate programming. The implementation
+details are presented in the following sections. The user documentation is in
+the @other-doc['(lib "phc-graph/scribblings/phc-graph.scrbl")] document.
+
+@(table-of-contents)
+
+@include-section[(submod "../traversal.hl.rkt" doc)]
+\ No newline at end of file
diff --git a/scribblings/phc-graph.scrbl b/scribblings/phc-graph.scrbl
@@ -2,8 +2,8 @@
@require[@for-label[phc-graph
racket/base]]
-@title{phc-graph}
-@author{georges}
+@title{Ph.C Graph library}
+@author[@author+email["Georges Dupéron" "georges.duperon@gmail.com"]]
@defmodule[phc-graph]
diff --git a/test/test-traversal-1.rkt b/test/test-traversal-1.rkt
@@ -0,0 +1,14 @@
+#lang typed/racket
+
+(require "../traversal.hl.rkt")
+
+(define-fold f₁ t₁ Null String)
+;(define-fold f₂ t₂ (Pairof Null Null) String)
+;(define-fold f₃ t₃ String String)
+;(define-fold f₄ t₄ (Pairof Null String) String)
+
+((f₁ string?
+ (λ ([x : String] [acc : Integer])
+ (values (string->symbol x) acc)))
+ '()
+ 0)
+\ No newline at end of file
diff --git a/traversal.hl.rkt b/traversal.hl.rkt
@@ -20,8 +20,18 @@
(require (for-label (submod ".."))))
@doc-lib-setup
-@title{Parametric replacement of parts of data structures, identified by their
- type}
+@title[#:style manual-doc-style
+ #:tag "traversal"
+ #:tag-prefix "phc-graph/traversal"]{Parametric replacement of parts of
+ data structures, identified by their type}
+
+@(chunks-toc-prefix
+ '("(lib phc-graph/scribblings/phc-graph-implementation.scrbl)"
+ "phc-graph/traversal"))
+
+@(table-of-contents)
+
+@(declare-exporting (lib "phc-graph/traversal.hl.rkt"))
@section{Introduction}
@@ -47,51 +57,128 @@ The second occurrence of @racket[(Listof String)], although semantically
equivalent to the type to replace, @racket[Foo], will not be altered, as it is
not expressed syntactically using the @racket[Foo] identifier.
-@defform[(define-fold name whole-type
- [type-to-replaceᵢ predicateᵢ] ...)]{
+@defform[(define-fold function-name type-name whole-type type-to-replaceᵢ ...)]{
The @racket[define-fold] macro takes the type of the whole data structure, and
a list of types to replace, each associated with a predicate for that type. It
- defines @racket[_name] as a macro, which behaves as follows:
-
- @(make-blockquote
- "leftindent"
- (flow-paragraphs
- (decode-flow
- (splice-run
- @defform[#:link-target? #f (_name function-name
- new-whole-type-name
- accumulator-type
- [new-typeᵢ update-functionᵢ] ...)]{
- Each @racket[update-functionᵢ] must have the type:
-
- @racketblock[(→ accumulator-type
- type-to-replaceᵢ
- (values accumulator-type new-typeᵢ))]
-
- This macro defines @racket[new-whole-type-name] as a type similar to
- @racket[whole-type], but with each syntactic occurrence of a
- @racket[type-to-replaceᵢ] replaced with the corresponding @racket[new-typeᵢ].
-
- This macro also defines @racket[function-name] as a function with the type:
-
- @racketblock[(→ accumulator-type
- whole-type
- (values accumulator-type new-whole-type-name))]
-
- The @racket[function-name] replaces all values in the whole data structure
- which are present in locations corresponding to a @racket[type-to-replaceᵢ].
- Each value is passed as an argument to the corresponding
- @racket[update-functionᵢ], and the result is used as a replacement.
-
- An accumulator value, with the type @racket[accumulator-type], is threaded
- through all calls to all @racket[update-functionᵢ], so that the update
- functions can share state in a functional way.}))))}
-
+ @;defines @racket[_name] as a macro, which behaves as follows:
+ defines @racket[(type-name Tᵢ ...)] as a polymorphic type, with one type
+ argument for each @racket[type-to-replaceᵢ], such that
+
+ @racketblock[(type-name type-to-replaceᵢ ...)]
+
+ is the same type as
+
+ @racketblock[whole-type]
+
+ In other words, @racket[type-name] is defined as @racket[whole-type], except
+ that each syntactic occurrence of a @racket[type-to-replaceᵢ] is replaced with
+ the corresponding type argument @racket[Tᵢ].
+
+ It also defines @racket[function-name] as a function, with the type
+
+ @racketblock[(∀ (Aᵢ ... Bᵢ ... Acc)
+ (→ (?@ (→ Any Boolean : Aᵢ)
+ (→ Aᵢ Acc (Values Bᵢ Acc)))
+ ...
+ (→ (type-name Aᵢ ...)
+ Acc
+ (Values (type-name Bᵢ ...)
+ Acc))))]
+
+ We use the @racket[?@] notation from
+ @racket[syntax/parse/experimental/template] to indicate that the function
+ accepts a predicate, followed by an update function, followed by another
+ predicate, and so on. For example, the function type when there are three
+ @racket[type-to-replaceᵢ] would be:
+
+ @racketblock[(∀ (A₁ A₂ A₃ B₁ B₂ B₃ Acc)
+ (→ (→ Any Boolean : A₁)
+ (→ A₁ Acc (Values B₁ Acc))
+ (→ Any Boolean : A₂)
+ (→ A₂ Acc (Values B₂ Acc))
+ (→ Any Boolean : A₃)
+ (→ A₃ Acc (Values B₃ Acc))
+ (→ (type-name A₁ A₂ A₃)
+ Acc
+ (Values (type-name B₁ B₂ B₃)
+ Acc))))]
+
+ The @racket[function-name] replaces all values in the whole data structure
+ which are present in locations corresponding to a @racket[type-to-replaceᵢ] in
+ the @racket[whole-type]. It expects those values to have the type @racket[Aᵢ],
+ i.e. its input type is not restricted to @racket[whole-type], any polymorphic
+ instance of @racket[type-name] is valid. Each value is passed as an argument
+ to the corresponding update function with type
+ @racket[(→ Aᵢ Acc (Values Bᵢ Acc))], and the result of type @racket[Bᵢ] is
+ used as a replacement.
+
+ An accumulator value, with the type @racket[Acc], is threaded through all
+ calls to all update functions, so that the update functions can communicate
+ state in a functional way.}
+
+
+* free-identifier-tree=?
+* cache of already-seen types
+* recursively go down the tree. If there are no replacements, return #f all the
+way up, so that a simple identity function can be applied in these cases.
@chunk[<define-fold>
- ]
+ (define-syntax define-fold
+ (syntax-parser
+ [(_ function-name:id
+ type-name:id
+ whole-type:type
+ type-to-replaceᵢ:type …)
+ <define-fold-prepare>
+ (template
+ (begin
+ <define-fold-result>))]))]
+
+@chunk[<define-fold-prepare>
+ (define-temp-ids "Tᵢ" (type-to-replaceᵢ …))
+ (define-temp-ids "Aᵢ" (type-to-replaceᵢ …))
+ (define-temp-ids "Bᵢ" (type-to-replaceᵢ …))
+ (define-temp-ids "predicateᵢ" (type-to-replaceᵢ …))
+ (define-temp-ids "updateᵢ" (type-to-replaceᵢ …))]
+
+@chunk[<define-fold-prepare>
+ (define/with-syntax (the-type the-code the-defs …)
+ (syntax-parse #'whole-type
+ #:literals (Null Pairof Listof List Vectorof Vector)
+ [Null #'(Null (values v acc))]
+ [(Pairof X Y)
+ #'(Null
+ (values v acc)
+ (define-fold fx tx X type-to-replaceᵢ …)
+ (define-fold fy ty Y type-to-replaceᵢ …))]
+ [#t #'((Pairof Any Any) (void))]))]
+
+@chunk[<define-fold-result>
+ the-defs …
+
+ (define-type (type-name Tᵢ …) the-type)
+
+ (: function-name (∀ (Aᵢ … Bᵢ … Acc)
+ (→ (?@ (→ Any Boolean : Aᵢ)
+ (→ Aᵢ Acc (Values Bᵢ Acc)))
+ …
+ (→ (type-name Aᵢ …)
+ Acc
+ (Values (type-name Bᵢ …)
+ Acc)))))
+ (define ((function-name (?@ predicateᵢ updateᵢ) …) v acc)
+ the-code)]
@section{Putting it all together}
@chunk[<*>
- ]
-\ No newline at end of file
+ (require phc-toolkit
+ (for-syntax racket/base
+ phc-toolkit/untyped
+ racket/syntax
+ syntax/parse
+ syntax/parse/experimental/template
+ type-expander/expander))
+
+ (provide define-fold)
+ <define-fold>]
+\ No newline at end of file
