commit 2bead71e16a19c106d911ae8bde84c4018620cfd
parent 5b5bbc3a1f3ca5eacd3d475a12401b0dd6a47615
Author: Georges Dupéron <georges.duperon@gmail.com>
Date: Thu, 20 Apr 2017 18:31:35 +0200
Moved implementation to main.rkt (part 2: update) + documentation
Diffstat:
4 files changed, 73 insertions(+), 38 deletions(-)
diff --git a/info.rkt b/info.rkt
@@ -3,10 +3,11 @@
(define deps '("base"
"rackunit-lib"
"type-expander"
- "typed-racket-lib"))
+ "typed-racket-lib"
+ "typed-racket-more"))
(define build-deps '("scribble-lib"
"racket-doc"))
-(define scribblings '(("scribblings/typed-worklist.scrbl" ())))
+(define scribblings '(("scribblings/typed-worklist.scrbl" () ("typed-racket"))))
(define pkg-desc "A Typed/Racket implementation of Kildall's worklist algorithm, with multiple worklists of different types.")
(define version "0.1")
(define pkg-authors '("Georges Dupéron"))
diff --git a/main.rkt b/main.rkt
@@ -144,11 +144,12 @@
(kons (O (car result)) (map i* (cdr result)))))
(: unwrap-io1 (∀ (A B) (→ (Listof (Pairof (I A) (O B)))
- (Listof (Pairof A B)))))
+ (HashTable A B))))
(define (unwrap-io1 l)
- (map (λ ([x : (Pairof (I A) (O B))])
- (kons (I-v (car x)) (O-v (cdr x))))
- l))
+ (make-immutable-hash
+ (map (λ ([x : (Pairof (I A) (O B))])
+ (kons (I-v (car x)) (O-v (cdr x))))
+ l)))
(define-syntax-rule (unwrap-io first-l (_ proc) ...)
(let*-values ([(new-l l) (values '() first-l)]
@@ -172,18 +173,3 @@
(i** roots)
(list (wrap-io proc) ...))
(proc 'dummy) ...))
-
-
-(worklist (list (list 7)
- (list))
- [(λ ([x : Integer])
- (list (number->string x)
- (list (if (> x 0) (sub1 x) 0))
- (list (string->symbol
- (string-append "v" (number->string x))))))
- (λ ([x : Symbol])
- (list (eq? 'v5 x)
- (list 10)
- (list 'xyz)))]
- (Integer String)
- (Symbol Boolean))
-\ No newline at end of file
diff --git a/scribblings/typed-worklist.scrbl b/scribblings/typed-worklist.scrbl
@@ -2,8 +2,27 @@
@(require (for-label typed-worklist
racket/base))
-@title{typed-worklist}
+@title{Typed worklist}
@author[@author+email["Georges Dupéron" "georges.duperon@gmail.com"]]
@defmodule[typed-worklist]
+@defform[(worklist roots [procᵢ …ₙ] [Inᵢ Outᵢ] …ₙ)
+ #:contracts
+ ([roots (List (Listof Inᵢ) …ₙ)]
+ [procᵢ (→ Inᵢ (List Outᵢ (Listof Inᵢ) …ₙ))]
+ [Inᵢ Type]
+ [Outᵢ Type])]{
+
+ Executes the corresponding @racket[procᵢ] on each element of each worklist.
+ The @racket[procᵢ] takes a value of type @racket[Inᵢ] and returns an output of
+ type @racket[Outᵢ], as well as @racket[n] lists of new inputs which are added
+ to the worklists.
+
+ The worklists are initialised with the given @racket[roots].
+
+ The whole expression has the following result type:
+
+ @racketblock[(List (HashTable Inᵢ Outᵢ) …ₙ)]
+
+ Within a worklist, duplicate elements are only processed once.}
+\ No newline at end of file
diff --git a/test/test-experiment.rkt b/test/test-experiment.rkt
@@ -1,16 +1,45 @@
#lang typed/racket
-(require "../experiment.rkt")
+(require typed-worklist
+ typed/rackunit)
-(worklist (list (list 7)
- (list))
- [(λ ([x : Integer])
- (list (number->string x)
- (list (if (> x 0) (sub1 x) 0))
- (list (string->symbol
- (string-append "v" (number->string x))))))
- (λ ([x : Symbol])
- (list (eq? 'v5 x)
- (list 10)
- (list 'xyz)))]
- (Integer String)
- (Symbol Boolean))
-\ No newline at end of file
+(let ()
+ (define result
+ (worklist (list (list 7)
+ (list))
+ [(λ ([x : Integer])
+ (list (number->string x)
+ (list (if (> x 0) (sub1 x) 0))
+ (list (string->symbol
+ (string-append "v" (number->string x))))))
+ (λ ([x : Symbol])
+ (list (eq? 'v5 x)
+ (list 10)
+ (list 'xyz)))]
+ (Integer String)
+ (Symbol Boolean)))
+ (ann result (List (HashTable Symbol Boolean) (HashTable Integer String)))
+ (check-equal?
+ result
+ '(#hash((v0 . #f)
+ (v1 . #f)
+ (v2 . #f)
+ (v3 . #f)
+ (v4 . #f)
+ (v5 . #t)
+ (v6 . #f)
+ (v7 . #f)
+ (v8 . #f)
+ (v9 . #f)
+ (v10 . #f)
+ (xyz . #f))
+ #hash((0 . "0")
+ (1 . "1")
+ (2 . "2")
+ (3 . "3")
+ (4 . "4")
+ (5 . "5")
+ (6 . "6")
+ (7 . "7")
+ (8 . "8")
+ (9 . "9")
+ (10 . "10")))))
+\ No newline at end of file
