GTP Benchmarks
1 Running a benchmark
1.1 Quick Route
1.2 Official Route
1.3 Semi-Auto Route
make-configurations
2 Version Notes
3 Benchmark Descriptions
3.1 acquire Description
3.2 dungeon Description
3.3 forth Description
3.4 fsm Description
3.5 gregor Description
3.6 jpeg Description
3.7 kcfa Description
3.8 lnm Description
3.9 mbta Description
3.10 morsecode Description
3.11 quad  U Description
3.12 quad  T Description
3.13 sieve Description
3.14 snake Description
3.15 suffixtree Description
3.16 synth Description
3.17 take5 Description
3.18 tetris Description
3.19 zombie Description
3.20 zordoz Description
4 Static Benchmark Details
4.1 Benchmark Size
4.2 Benchmark Types
4.2.1 acquire Boundary Types
4.2.2 dungeon Boundary Types
4.2.3 forth Boundary Types
4.2.4 fsm Boundary Types
4.2.5 fsmoo Boundary Types
4.2.6 gregor Boundary Types
4.2.7 jpeg Boundary Types
4.2.8 kcfa Boundary Types
4.2.9 lnm Boundary Types
4.2.10 mbta Boundary Types
4.2.11 morsecode Boundary Types
4.2.12 quad  T Boundary Types
4.2.13 quad  U Boundary Types
4.2.14 sieve Boundary Types
4.2.15 snake Boundary Types
4.2.16 suffixtree Boundary Types
4.2.17 synth Boundary Types
4.2.18 take5 Boundary Types
4.2.19 tetris Boundary Types
4.2.20 zombie Boundary Types
4.2.21 zordoz Boundary Types
5 Dynamic Benchmark Details
5.1 Time and Garbage Collection Details
5.2 Chaperones Details
6 Reproducibility
6.1 Module Dependence Graphs
make-modulegraph
modulegraph?
complete-path->imported-modules
complete-path->exported-identifiers
6.2 Size Information
benchmark-size-info
6.3 Type Information
compile/  require-typed-check-info
6.4 Counting Chaperones
count-chaperones
racket-bin/  count-chaperones?
chaperones-count/  c
Bibliography
8.12

GTP Benchmarks🔗ℹ

GTP = gradual typing performance

Latest Version: 9.2.1

Source: https://github.com/bennn/gtp-benchmarks

This package contains benchmarks for measuring the cost of typed/untyped interaction in Typed Racket [REP-2023].

Always include a version number when reporting data on these benchmarks.

image

1 Running a benchmark🔗ℹ

There are three ways to run a benchmark: either by copying code, using the gtp-measure package, or running a setup script.

1.1 Quick Route🔗ℹ

1.2 Official Route🔗ℹ

1.3 Semi-Auto Route🔗ℹ

Script for generating all typed/untyped configurations of a benchmark.

procedure

(make-configurations dir)  void?

  dir : (and/c path-string? directory-exists?)
Given a path to a benchmark (under the "benchmarks/" directory), generates all typed/untyped configurations of the benchmark and stores them in a new folder in the current directory.

2 Version Notes🔗ℹ

See also the GitHub release notes: https://github.com/bennn/gtp-benchmarks/releases

3 Benchmark Descriptions🔗ℹ

This section has summaries of the benchmark programs.

In each description, the author and source fields credit the authors of the code that inspired the benchmarks. The dependencies field lists any libraries outside the core of Racket and Typed Racket that the benchmarks use; we assume that programmers who use gradual typing cannot change the language of these libraries (the libraries are either typed or untyped).

Each benchmark comes with a short description of its behavior, a module dependence graph, and the names of its migratable and fixed modules. In the module graphs, edges point from one module to another whenever one module requires another. Nodes for migratable modules are circles — these are the modules we apply gradual typing to. Nodes for fixed modules are squares — these modules are the same in all configurations.

Note: these graphs do not show type adaptor modules.

3.1 acquire Description🔗ℹ


author: Matthias Felleisen
source: github.com/mfelleisen/Acquire
dependencies: None
Simulates a board game between player objects. The players send messages to an administrator object; the administrator enforces the rules of the game.
image

0. admin.rkt

  

3. board.rkt

  

6. state.rkt

  

9. ../base/untyped.rkt

1. auxiliaries.rkt

  

4. main.rkt

  

7. strategy.rkt

  

2. basics.rkt

  

5. player.rkt

  

8. tree.rkt

  

3.2 dungeon Description🔗ℹ


author: Vincent St-Amour
source: github.com/stamourv/dungeons-and-repossessions
dependencies: None
Builds a maze of wall and floor objects by drawing first-class classes from a list.
image

0. cell.rkt

  

2. main.rkt

  

4. utils.rkt

1. grid.rkt

  

3. message-queue.rkt

  

5. ../base/un-types.rkt

3.3 forth Description🔗ℹ


author: Ben Greenman
source: github.com/bennn/forth
dependencies: None
Interprets Forth programs. The interpreter represents calculator commands as a list of first-class objects.

Note: this benchmark runs very quickly untyped (< 50 milliseconds), and extremely slowly with certain type boundaries. As the extreme slowdowns improve, we plan to increase the input size so the untyped configuration runs in the 1-2 second range.

Changed in version 0.2: Increased input size, thanks to Typed Racket improvements (ff2956d).


image

0. command.rkt

  

1. eval.rkt

  

2. main.rkt

  

3. stack.rkt

3.4 fsm Description🔗ℹ


author: Linh Chi Nguyen
source: github.com/ayaderaghul/sample-fsm
dependencies: None
Simulates an economy with finite-state automata. The economy is implemented as a vector; this vector repeatedly crosses between modules in the benchmark.

fsmoo is similar, but implements the economy as an object.
image

0. automata.rkt

  

1. main.rkt

  

2. population.rkt

  

3. utilities.rkt

3.5 gregor Description🔗ℹ


author: Jon Zeppieri
source: github.com/97jaz/gregor
dependencies: cldr (untyped) and tzinfo (untyped)
Provides tools for manipulating calendar dates. The benchmark builds tens of date values and runs unit tests on these values.
image

0. clock.rkt

  

4. difference.rkt

  

8. moment-base.rkt

  

12. ymd.rkt

1. core-structs.rkt

  

5. gregor-structs.rkt

  

9. moment.rkt

  

13. ../base/tzinfo/main.rkt

2. date.rkt

  

6. hmsn.rkt

  

10. offset-resolvers.rkt

  

3. datetime.rkt

  

7. main.rkt

  

11. time.rkt

  

3.6 jpeg Description🔗ℹ


author: Andy Wingo
source: github.com/wingo/racket-jpeg
dependencies: math/array (typed) and rnrs/bytevectors-6 (untyped)
Parses a bytestream of JPEG data to an internal representation, then serializes the result.
image

0. bit-ports.rkt

  

2. huffman.rkt

  

4. main.rkt

  

6. ../base/untyped.rkt

1. exif.rkt

  

3. jfif.rkt

  

5. ../base/math/array.rkt

  

3.7 kcfa Description🔗ℹ


author: Matt Might
source: matt.might.net/articles/implementation-of-kcfa-and-0cfa/
dependencies: None
Performs 2-CFA on a lambda calculus equation built from Church numerals; specifically, it analyzes an encoding of (2 * (1 + 3)) = (1 * 2) (provided by Dee Glaze via [OAAM] (church-num) via [CFA2]).
image

0. ai.rkt

  

2. denotable.rkt

  

4. structs.rkt

  

6. ui.rkt

1. benv.rkt

  

3. main.rkt

  

5. time.rkt

  

3.8 lnm Description🔗ℹ


author: Ben Greenman
source: github.com/nuprl/gradual-typing-performance/tree/master/paper/popl-2016/scripts
dependencies: plot (typed) and math/statistics (typed)
Renders a plot and spreadsheet for some gradual typing data. Two modules in this benchmark are tightly-coupled to Typed Racket libraries; typing both modules improves performance.
image

0. bitstring.rkt

  

2. main.rkt

  

4. spreadsheet.rkt

1. lnm-plot.rkt

  

3. modulegraph.rkt

  

5. summary.rkt

3.9 mbta Description🔗ℹ


author: Matthias Felleisen
source: ?
dependencies: graph (untyped)
Builds a map of Boston’s subway system and answers reachability queries. The map encapsulates a boundary to Racket’s untyped graph library; when the map is typed, the boundary to graph is a performance bottleneck.
image

0. main.rkt

  

2. t-graph.rkt

  

4. ../base/my-graph.rkt

1. run-t.rkt

  

3. t-view.rkt

  

3.10 morsecode Description🔗ℹ


authors: John B. Clements and Neil Van Dyke
source: github.com/jbclements/morse-code-trainer/tree/master/morse-code-trainer
dependencies: None
Computes Levenshtein distances and morse code translations for a sequence of pairs of words.
image

0. levenshtein.rkt

  

1. main.rkt

  

2. morse-code-strings.rkt

  

3. morse-code-table.rkt

3.11 quadU Description🔗ℹ


author: Ben Greenman
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format. This benchmark started from an untyped program by the original author. For the benchmark, we added types with minimal changes to the code.
image

0. hyphenate.rkt

  

4. ocm.rkt

  

8. quick-sample.rkt

  

12. world.rkt

1. main.rkt

  

5. penalty-struct.rkt

  

9. render.rkt

  

13. wrap.rkt

2. measure.rkt

  

6. quad-main.rkt

  

10. sugar-list.rkt

  

14. ../base/csp/csp.rkt

3. ocm-struct.rkt

  

7. quads.rkt

  

11. utils.rkt

  

15. ../base/quad-types.rkt

3.12 quadT Description🔗ℹ


author: Matthew Butterick
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format. This benchmark started from a typed program by the original author. For the benchmark, we removed types with minimal changes to the code. Any cast forms changed to analogous contract forms, and any define-predicate forms changed to functions or contracts.
image

0. hyphenate.rkt

  

5. penalty-struct.rkt

  

10. sugar-list.rkt

  

15. ../base/untyped-predicates.rkt

1. main.rkt

  

6. quad-main.rkt

  

11. utils.rkt

  

16. ../base/untyped.rkt

2. measure.rkt

  

7. quads.rkt

  

12. world.rkt

  

3. ocm-struct.rkt

  

8. quick-sample.rkt

  

13. wrap.rkt

  

4. ocm.rkt

  

9. render.rkt

  

14. ../base/csp/csp.rkt

  

3.13 sieve Description🔗ℹ


author: Ben Greenman
source: github.com/nuprl/gradual-typing-performance/tree/master/benchmarks/sieve
dependencies: None
Computes prime numbers using a stream library.
image

0. main.rkt

  

1. streams.rkt

3.14 snake Description🔗ℹ


author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Functional program that implements the Snake game. The benchmark folds over a sequence of game moves.
image

0. collide.rkt

  

2. cut-tail.rkt

  

4. handlers.rkt

  

6. motion-help.rkt

1. const.rkt

  

3. data.rkt

  

5. main.rkt

  

7. motion.rkt

3.15 suffixtree Description🔗ℹ


author: Danny Yoo
source: github.com/dyoo/suffixtree
dependencies: None
Computes longest common subsequences between strings.
image

0. data.rkt

  

2. lcs.rkt

  

4. structs.rkt

1. label.rkt

  

3. main.rkt

  

5. ukkonen.rkt

3.16 synth Description🔗ℹ


author: Vincent St. Amour & Neil Toronto
source: github.com/stamourv/synth
dependencies: None
Converts a description of notes and drum beats to WAV format. This benchmark creates a large number of vectors (to represent notes) but rarely reads from the vectors.
image

0. array-broadcast.rkt

  

3. array-utils.rkt

  

6. main.rkt

  

9. synth.rkt

1. array-struct.rkt

  

4. data.rkt

  

7. mixer.rkt

  

2. array-transform.rkt

  

5. drum.rkt

  

8. sequencer.rkt

  

3.17 take5 Description🔗ℹ


author: Matthias Felleisen
source: github.com/mfelleisen/take5
dependencies: None
Simulates a card game between player objects. The players communicate through a dealer object.
image

0. basics.rkt

  

3. dealer.rkt

  

6. player.rkt

1. card-pool.rkt

  

4. deck.rkt

  

7. stack.rkt

2. card.rkt

  

5. main.rkt

  

8. ../base/untyped.rkt

3.18 tetris Description🔗ℹ


author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Functional implementation of Tetris; the benchmark replays a pre-recorded sequence of moves.
image

0. aux.rkt

  

3. consts.rkt

  

6. main.rkt

1. block.rkt

  

4. data.rkt

  

7. tetras.rkt

2. bset.rkt

  

5. elim.rkt

  

8. world.rkt

3.19 zombie Description🔗ℹ


author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Implements a game where players avoid enemies. This benchmark uses an encoding of objects as higher-order functions to implement the game player, the enemies, and the board.
image

0. image.rkt

  

1. main.rkt

  

2. math.rkt

  

3. zombie.rkt

3.20 zordoz Description🔗ℹ


author: Ben Greenman
source: github.com/bennn/zordoz
dependencies: compiler/zo-parse (untyped) and compiler/zo-structs (untyped)
Traverses Racket bytecode (.zo files). The compiler library defines the bytecode data structures.
image

0. main.rkt

  

2. zo-shell.rkt

  

4. zo-transition.rkt

  

6. ../base/compiler-zo-structs.rkt

1. zo-find.rkt

  

3. zo-string.rkt

  

5. ../base/compiler-zo-parse.rkt

  

7. ../base/typed-zo-structs.rkt

4 Static Benchmark Details🔗ℹ

4.1 Benchmark Size🔗ℹ

Benchmark

  

Untyped LOC

  

Annotation LOC

  

# Modules

  

# Bnd.

  

# Exp.

acquire

  

1654

  

304

  

9

  

26

  

106

dungeon

  

541

  

69

  

5

  

5

  

38

forth

  

257

  

31

  

4

  

4

  

10

fsm

  

182

  

56

  

4

  

5

  

17

fsmoo

  

194

  

83

  

4

  

4

  

9

gregor

  

945

  

175

  

13

  

42

  

142

jpeg

  

1432

  

165

  

5

  

5

  

50

kcfa

  

230

  

53

  

7

  

17

  

62

lnm

  

488

  

114

  

6

  

8

  

28

mbta

  

266

  

71

  

4

  

3

  

8

morsecode

  

159

  

38

  

4

  

3

  

15

quadT

  

6685

  

307

  

14

  

27

  

174

quadU

  

6779

  

221

  

14

  

27

  

160

sieve

  

35

  

17

  

2

  

1

  

9

snake

  

159

  

50

  

8

  

16

  

31

suffixtree

  

537

  

130

  

6

  

11

  

69

synth

  

837

  

138

  

10

  

26

  

51

take5

  

318

  

34

  

8

  

14

  

26

tetris

  

249

  

107

  

9

  

23

  

58

zombie

  

300

  

25

  

4

  

3

  

15

zordoz

  

1393

  

223

  

5

  

6

  

12

Figure 1: Size of the benchmarks.

The table in figure 1 quantifies the benchmarks’ size and structure. The Untyped LOC column lists the number of non-whitespace, non-comment lines of code in the untyped version of each benchmark (computed by the syntax-sloc library). The Annotation LOC is the additional number of lines in the typed version of each benchmark; this estimates the number of type annotations in the typed version. The # Modules column is the number of modules in each benchmark, and lastly the # Bnd. and # Exp. columns summarize the dependencies between these modules. One boundary (counted in # Bnd.) is one import statement from one module in the benchmark to another. One export (counted in # Exp.) is one identifier provided by one module in the benchmark.

4.2 Benchmark Types🔗ℹ

This section contains the source code for each boundary between modules in the benchmarks. The data format is:

benchmark name
importing module

'(require-typed-check exporting-module ...)

In other words, the data below shows the require/typed/check forms for each module in each benchmark.

Depending on the configuration, a require/typed/check expands to either a require or a require/typed form. The latter form compiles types to contracts; these contracts are the reason why some configurations run slower than others. In this way, the types below give an idea of the kind of overhead each benchmark may suffer from.

Note: the data below may refer to type aliases. See the source code for each benchmark to find what the aliases stand for.

4.2.1 acquire Boundary Types🔗ℹ


admin.rkt

'(require/typed/check

  "basics.rkt"

  (ALL-HOTELS (Listof Hotel))

  (hotel? (-> Any Boolean))

  (shares-available? (-> Shares (Listof Hotel) Boolean))

  (shares? (-> Any Boolean))

  (shares-order? (-> Any Boolean)))


basics.rkt

'(require/typed/check

  "auxiliaries.rkt"

  (randomly-pick (-> (Listof Hotel) Hotel)))


board-adapted.rkt

'(require/typed/check

  "board.rkt"

  (#:struct tile ((column : Column) (row : Row)))

  (tile<=? (-> Tile Tile Boolean))

  (tile->string (-> Tile String))

  (ALL-TILES (Listof Tile))

  (STARTER-TILES# Natural)

  (FOUNDING 'FOUNDING)

  (GROWING 'GROWING)

  (MERGING 'MERGING)

  (SINGLETON 'SINGLETON)

  (IMPOSSIBLE 'IMPOSSIBLE)

  (deduplicate/hotel (-> (Listof Hotel) (Listof Hotel)))

  (make-board (-> Board))

  (board-tiles (-> Board (Listof Tile)))

  (what-kind-of-spot (-> Board Tile SpotType))

  (growing-which (-> Board Tile (Option Hotel)))

  (merging-which

   (-> Board Tile (Values (Pairof Hotel (Listof Hotel)) (Listof Hotel))))

  (size-of-hotel (-> Board Hotel Natural))

  (free-spot? (-> Board Tile Boolean))

  (merge-hotels (-> Board Tile Hotel Board))

  (found-hotel (-> Board Tile Hotel Board))

  (grow-hotel (-> Board Tile Board))

  (place-tile (-> Board Tile Board))

  (set-board (-> Board Tile Kind (Option Hotel) Board))

  (affordable? (-> Board (Listof Hotel) Cash Boolean))

  (*create-board-with-hotels

   (-> (Listof Tile) (Listof (Pairof Hotel (Listof Tile))) Board))

  (distinct-and-properly-formed

   (-> (Listof Tile) (-> (Listof (Pairof Hotel (Listof Tile))) Boolean))))


board.rkt

'(require/typed/check

  "auxiliaries.rkt"

  (aux:partition

   (All (A B) (-> (Listof A) (-> A Real) (-> A B) (Listof (Listof B)))))

  (distinct (-> (Listof Any) Boolean))

  (randomly-pick (All (A) (-> (Listof A) A))))

'(require/typed/check

  "basics.rkt"

  (hotel? (-> Any Boolean))

  (SAFE# Natural)

  (price-per-share (-> Hotel Natural (Option Cash)))

  (shares-order? (-> Any Boolean))

  (hotel->color (-> Hotel Color))

  (hotel->label (-> Hotel String)))


main.rkt

'(require/typed/check "admin.rkt" (administrator% Administrator%))

'(require/typed/check

  "auxiliaries.rkt"

  (randomly-pick (-> (Listof Tile) Tile)))

'(require/typed/check

  "player.rkt"

  (random-players (-> Natural (Listof (Instance Player%))))

  (ordered-players (-> Natural (Listof (Instance Player%))))

  (inf-loop-player (-> Natural (Instance Player%))))


player.rkt

'(require/typed/check

  "admin.rkt"

  (administrator% Administrator%)

  (turn% Turn%))

'(require/typed/check

  "basics.rkt"

  (player-shares0 Shares)

  (*combine-shares (-> (Listof Shares) Shares))

  (shares-minus (-> Shares Shares Shares))

  (banker-shares0 Shares))

'(require/typed/check "strategy.rkt" (ordered-s Strategy) (random-s Strategy))


state-adapted.rkt

'(require/typed/check

  "state.rkt"

  (score? (-> Any Boolean))

  (#:struct

   player

   ((name : String)

    (tiles : (Listof Tile))

    (money : Cash)

    (shares : Shares)

    (external : (Option (Instance Player%)))))

  (#:struct

   state

   ((board : Board)

    (players : (Listof Player))

    (tiles : (Listof Tile))

    (hotels : (Listof Hotel))

    (shares : Shares)

    (bad : (Listof Player))))

  (*create-player (-> String Cash Shares (Listof Tile) Player))

  (player0 (-> String Tile Tile Tile Tile Tile Tile (Instance Player%) Player))

  (state0 (-> Player * State))

  (state-sub-shares (-> State Shares State))

  (*cs0 (-> String * State))

  (*create-state (-> Board (Listof Player) State))

  (state-place-tile (->* (State Tile) ((Option Hotel)) State))

  (state-move-tile (-> State Tile State))

  (state-next-turn (-> State State))

  (state-remove-current-player (-> State State))

  (state-eliminate (-> State (Listof Player) State))

  (state-current-player (-> State Player))

  (state-buy-shares (-> State (Listof Hotel) State))

  (state-return-shares (->* (State Decisions) (Board) State))

  (state-score (-> State (Listof (List String Cash))))

  (state-final? (-> State Boolean)))


state.rkt

'(require/typed/check

  "auxiliaries.rkt"

  (aux:partition

   (All (A B) (-> (Listof A) (-> A Real) (-> A B) (Listof (Listof B)))))

  (distinct (-> (Listof Any) Boolean)))

'(require/typed/check

  "basics.rkt"

  (ALL-HOTELS (Listof Hotel))

  (CASH0 Cash)

  (FINAL# Natural)

  (SAFE# Natural)

  (banker-shares0 Shares)

  (bonus (-> M*ority Hotel Natural Cash))

  (cash? (-> Any Boolean))

  (player-shares0 Shares)

  (price-per-share (-> Hotel Natural (Option Cash)))

  (shares++ (-> Shares Hotel Shares))

  (shares-- (-> Shares Hotel Shares))

  (shares->string (-> Shares String))

  (shares-available (-> Shares Hotel Share))

  (shares-available? (-> Shares (Listof Hotel) Boolean))

  (shares-combinable? (-> (Listof Shares) Boolean))

  (shares-order? (-> Any Boolean))

  (shares-minus (-> Shares Shares Shares))

  (shares-plus (-> Shares Shares Shares)))


strategy.rkt

'(require/typed/check

  "auxiliaries.rkt"

  (randomly-pick (All (A) (-> (Listof A) A))))

'(require/typed/check

  "basics.rkt"

  (ALL-HOTELS (Listof Hotel))

  (SHARES-PER-TURN# Integer)

  (hotel<=? (-> Hotel Hotel Boolean))

  (price-per-share (-> Hotel Natural (Option Cash)))

  (shares++ (-> Shares Hotel Shares))

  (shares-- (-> Shares Hotel Shares))

  (shares-available (-> Shares Hotel Share)))


tree.rkt

'(require/typed/check

  "basics.rkt"

  (shares-available? (-> Shares (Listof Hotel) Boolean))

  (shares-order? (-> Any Boolean)))


4.2.2 dungeon Boundary Types🔗ℹ


cell.rkt

'(require/typed/check "message-queue.rkt" (enqueue-message! (-> String Void)))


grid.rkt

'(require/typed/check

  "cell.rkt"

  (char->cell% (-> Char Cell%))

  (void-cell% Cell%))


main.rkt

'(require/typed/check

  "cell.rkt"

  (void-cell% Cell%)

  (wall% Cell%)

  (door% Door%)

  (vertical-door% Door%)

  (horizontal-door% Door%)

  (horizontal-wall% Cell%)

  (four-corner-wall% Cell%)

  (pillar% Cell%)

  (vertical-wall% Cell%)

  (north-west-wall% Cell%)

  (north-east-wall% Cell%)

  (south-west-wall% Cell%)

  (south-east-wall% Cell%)

  (north-tee-wall% Cell%)

  (west-tee-wall% Cell%)

  (east-tee-wall% Cell%)

  (south-tee-wall% Cell%)

  (empty-cell% Cell%))

'(require/typed/check

  "grid.rkt"

  (array-set! (-> Grid Pos (Instance Cell%) Void))

  (build-array (-> Pos (-> Any (Instance Cell%)) Grid))

  (left (->* (Pos) (Index) Pos))

  (right (->* (Pos) (Index) Pos))

  (up (->* (Pos) (Index) Pos))

  (down (->* (Pos) (Index) Pos))

  (grid-ref (-> Grid Pos (U #f (Instance Cell%))))

  (grid-height (-> Grid Index))

  (grid-width (-> Grid Index))

  (show-grid (-> Grid String)))

'(require/typed/check

  "utils.rkt"

  (random (-> Integer Natural))

  (random-between (-> Integer Integer Integer))

  (random-from (All (A) (-> (Listof A) A)))

  (reset! (-> Void)))


4.2.3 forth Boundary Types🔗ℹ


command.rkt

'(require/typed/check

  "stack.rkt"

  (stack-drop (-> Stack Stack))

  (stack-dup (-> Stack Stack))

  (stack-init (-> Stack))

  (stack-over (-> Stack Stack))

  (stack-pop (-> Stack (Values Integer Stack)))

  (stack-push (-> Stack Integer Stack))

  (stack-swap (-> Stack Stack)))


eval.rkt

'(require/typed/check

  "command.rkt"

  (CMD* (Listof (Instance Command%)))

  (command% Command%))

'(require/typed/check "stack.rkt" (stack-init (-> Stack)))


main.rkt

'(require/typed/check

  "eval.rkt"

  (forth-eval* (-> (Listof String) (Values Any Any))))


4.2.4 fsm Boundary Types🔗ℹ


main.rkt

'(require/typed/check

  "population.rkt"

  (build-random-population (-> Natural Population))

  (population-payoffs (-> Population (Listof Payoff)))

  (death-birth (-> Population Natural (#:random (U False Real)) Population))

  (match-up* (-> Population Natural Population)))

'(require/typed/check

  "utilities.rkt"

  (relative-average (-> (Listof Real) Real Real)))


population.rkt

'(require/typed/check

  "utilities.rkt"

  (choose-randomly

   (->

    (Listof Probability)

    Natural

    (#:random (U False Real))

    (Listof Natural))))


4.2.5 fsmoo Boundary Types🔗ℹ


automata-adapted.rkt

'(require/typed/check

  "automata.rkt"

  (make-random-automaton (-> Natural oAutomaton)))


main.rkt

'(require/typed/check

  "utilities.rkt"

  (relative-average (-> (Listof Real) Real Real)))


population-adapted.rkt

'(require/typed/check

  "population.rkt"

  (build-random-population (-> Natural oPopulation)))


population.rkt

'(require/typed/check

  "utilities.rkt"

  (choose-randomly

   (->

    (Listof Probability)

    Natural

    (#:random (U False Real))

    (Listof Natural))))


4.2.6 gregor Boundary Types🔗ℹ


clock.rkt

'(require/typed/check

  "datetime.rkt"

  (datetime->date (-> DateTime Date))

  (datetime->time (-> DateTime Time)))

'(require/typed/check

  "moment.rkt"

  (current-timezone (Parameterof (U tz #f)))

  (posix->moment (-> Exact-Rational tz Moment))

  (moment->datetime/local (-> Moment DateTime))

  (UTC String)

  (moment

   (->*

    (Natural)

    (Month

     Natural

     Natural

     Natural

     Natural

     Natural

     #:tz

     (U tz #f)

     #:resolve-offset

     (-> (U tzgap tzoverlap) DateTime (U String #f) (U #f Moment) Moment))

    Moment))

  (moment=? (-> Moment Moment Boolean))

  (moment->iso8601 (-> Moment String))

  (moment->iso8601/tzid (-> Moment String)))


core-adapter.rkt

'(require/typed/check

  "core-structs.rkt"

  (#:struct YMD ((y : Natural) (m : Month) (d : Natural)))

  (#:struct HMSN ((h : Integer) (m : Integer) (s : Integer) (n : Integer))))


date.rkt

'(require/typed/check

  "ymd.rkt"

  (ymd->jdn (-> YMD Integer))

  (jdn->ymd (-> Exact-Rational YMD))

  (jdn->iso-wday (-> Integer (U 1 2 3 4 5 6 7)))

  (ymd->yday (-> YMD Natural))

  (iso-weeks-in-year (-> Natural (U 52 53))))


datetime.rkt

'(require/typed/check

  "date.rkt"

  (date->iso8601 (-> Date String))

  (date->jdn (-> Date Integer))

  (jdn->date (-> Integer Date))

  (date->ymd (-> Date YMD))

  (date (->* (Natural) (Month Natural) Date))

  (date=? (-> Date Date Boolean)))

'(require/typed/check "hmsn.rkt" (NS/DAY Natural) (NS/SECOND Natural))

'(require/typed/check

  "time.rkt"

  (time->iso8601 (-> Time String))

  (time->ns (-> Time Natural))

  (day-ns->time (-> Natural Time))

  (make-time (->* (Integer) (Integer Integer Integer) Time))

  (time=? (-> Time Time Boolean)))


difference.rkt

'(require/typed/check

  "date.rkt"

  (date->ymd (-> Date YMD))

  (date (->* (Natural) (Month Natural) Date)))

'(require/typed/check

  "datetime.rkt"

  (datetime<? (-> DateTime DateTime Boolean))

  (datetime->date (-> DateTime Date))

  (date+time->datetime (-> Date Time DateTime))

  (datetime->time (-> DateTime Time))

  (datetime->jd (-> DateTime Exact-Rational))

  (datetime

   (->* (Natural) (Month Natural Natural Natural Natural Natural) DateTime)))

'(require/typed/check "hmsn.rkt" (NS/DAY Natural))

'(require/typed/check

  "ymd.rkt"

  (days-in-month (-> Natural Month (U 28 29 30 31))))


gregor-adapter.rkt

'(require/typed/check

  "gregor-structs.rkt"

  (#:struct Date ((ymd : YMD) (jdn : Integer)))

  (#:struct Time ((hmsn : HMSN) (ns : Natural)))

  (#:struct DateTime ((date : Date) (time : Time) (jd : Exact-Rational)))

  (#:struct

   Moment

   ((datetime/local : DateTime)

    (utc-offset : Integer)

    (zone : (U String #f)))))


main.rkt

'(require/typed/check

  "clock.rkt"

  (current-clock (Parameterof (-> Exact-Rational)))

  (today/utc (-> Date))

  (today (->* () (#:tz (U tz #f)) Date))

  (current-time/utc (-> Time))

  (current-time (->* () (#:tz (U tz #f)) Time))

  (now/utc (-> DateTime))

  (now (->* () (#:tz (U tz #f)) DateTime))

  (now/moment/utc (-> Moment))

  (now/moment (-> Moment)))

'(require/typed/check

  "date.rkt"

  (date=? (-> Date Date Boolean))

  (date (->* (Natural) (Month Natural) Date))

  (date->iso8601 (-> Date String)))

'(require/typed/check

  "datetime.rkt"

  (datetime=? (-> DateTime DateTime Boolean))

  (datetime<=? (-> DateTime DateTime Boolean))

  (datetime

   (->* (Natural) (Month Natural Natural Natural Natural Natural) DateTime))

  (datetime->time (-> DateTime Time))

  (datetime->date (-> DateTime Date))

  (datetime->iso8601 (-> DateTime String))

  (datetime->posix (-> DateTime Exact-Rational)))

'(require/typed/check

  "difference.rkt"

  (datetime-months-between (-> DateTime DateTime Integer))

  (datetime-days-between (-> DateTime DateTime Integer))

  (datetime-nanoseconds-between (-> DateTime DateTime Integer)))

'(require/typed/check

  "moment.rkt"

  (current-timezone (Parameterof (U tz #f)))

  (moment

   (->*

    (Natural)

    (Month

     Natural

     Natural

     Natural

     Natural

     Natural

     #:tz

     (U tz #f)

     #:resolve-offset

     (-> (U tzgap tzoverlap) DateTime (U String #f) (U #f Moment) Moment))

    Moment))

  (moment=? (-> Moment Moment Boolean))

  (UTC String)

  (moment->iso8601/tzid (-> Moment String))

  (posix->moment (-> Exact-Rational tz Moment)))

'(require/typed/check

  "time.rkt"

  (time=? (-> Time Time Boolean))

  (time->iso8601 (-> Time String))

  (make-time (->* (Integer) (Integer Integer Integer) Time)))


moment-base.rkt

'(require/typed/check "datetime.rkt" (datetime->iso8601 (-> DateTime String)))


moment.rkt

'(require/typed/check

  "datetime.rkt"

  (datetime

   (->* (Natural) (Month Natural Natural Natural Natural Natural) DateTime))

  (datetime->posix (-> DateTime Exact-Rational))

  (posix->datetime (-> Exact-Rational DateTime))

  (datetime->jd (-> DateTime Exact-Rational))

  (datetime-add-seconds (-> DateTime Integer DateTime)))

'(require/typed/check "hmsn.rkt" (NS/SECOND Natural))

'(require/typed/check

  "moment-base.rkt"

  (make-moment (-> DateTime Integer (U String #f) Moment))

  (moment->iso8601 (-> Moment String))

  (moment->iso8601/tzid (-> Moment String)))

'(require/typed/check

  "offset-resolvers.rkt"

  (resolve-offset/raise

   (-> (U tzgap tzoverlap) DateTime (U String #f) (U Moment #f) Moment)))


offset-resolvers.rkt

'(require/typed/check

  "datetime.rkt"

  (datetime->iso8601 (-> DateTime String))

  (posix->datetime (-> Exact-Rational DateTime))

  (datetime->posix (-> DateTime Exact-Rational))

  (datetime

   (->* (Natural) (Month Natural Natural Natural Natural Natural) DateTime))

  (datetime->jd (-> DateTime Exact-Rational))

  (datetime-add-seconds (-> DateTime Integer DateTime)))

'(require/typed/check "hmsn.rkt" (NS/SECOND Natural))

'(require/typed/check

  "moment-base.rkt"

  (make-moment (-> DateTime Integer (U String #f) Moment))

  (moment->iso8601 (-> Moment String))

  (moment->iso8601/tzid (-> Moment String)))


time.rkt

'(require/typed/check

  "hmsn.rkt"

  (hmsn->day-ns (-> HMSN Natural))

  (day-ns->hmsn (-> Natural HMSN))

  (NS/SECOND Natural))


4.2.7 jpeg Boundary Types🔗ℹ


huffman.rkt

'(require/typed/check "bit-ports.rkt" (read-bit (-> Bit-Port Integer)))


jfif.rkt

'(require/typed/check

  "bit-ports.rkt"

  (make-bit-port (-> Port Bit-Port))

  (read-signed-bits (-> Bit-Port Natural Integer))

  (write-bits (-> Bit-Port Integer Natural Void))

  (flush-bits (-> Bit-Port Void)))

'(require/typed/check

  "huffman.rkt"

  (make-huffman-table (-> Bytes Bytes Huffman))

  (read-huffman-coded-value (-> Bit-Port Huffman Byte))

  (compute-huffman-table-for-freqs (-> Q-Table Huffman)))


main.rkt

'(require/typed/check "exif.rkt" (parse-exif (-> Bytes (Listof PTs))))

'(require/typed/check

  "jfif.rkt"

  (#:struct

   jfif

   ((frame : frame) (misc-segments : (Listof misc)) (mcu-array : (Array MCU))))

  (#:struct

   frame

   ((marker : Natural)

    (precision : Byte)

    (y : Natural)

    (x : Natural)

    (components : (Vectorof component))

    (samp-x : Natural)

    (samp-y : Natural)))

  (#:struct

   component

   ((id : Byte)

    (index : Natural)

    (samp-x : Natural)

    (samp-y : Natural)

    (q-table : Natural)))

  (#:struct misc ((marker : Natural) (bytes : Bytes)))

  (#:struct

   params

   ((q-tables : QT*)

    (dc-tables : H*)

    (ac-tables : H*)

    (restart-interval : Natural)

    (misc-segments : (Listof misc))))

  (read-jfif

   (->*

    ((U String Bytes Input-Port))

    (#:with-body? Boolean #:with-misc-sections? Boolean)

    jfif))

  (write-jfif (-> (U String Output-Port) jfif Void)))


4.2.8 kcfa Boundary Types🔗ℹ


benv-adapted.rkt

'(require/typed/check

  "benv.rkt"

  (#:struct Closure ((lam : Lam) (benv : BEnv)))

  (#:struct Binding ((var : Var) (time : Time)))

  (empty-benv BEnv)

  (benv-lookup (-> BEnv Var Addr))

  (benv-extend (-> BEnv Var Addr BEnv))

  (benv-extend* (-> BEnv (Listof Var) (Listof Addr) BEnv)))


denotable-adapted.rkt

'(require/typed/check

  "denotable.rkt"

  (#:struct State ((call : Exp) (benv : BEnv) (store : Store) (time : Time)))

  (d-bot Denotable)

  (d-join (-> Denotable Denotable Denotable))

  (empty-store Store)

  (store-lookup (-> Store Addr Denotable))

  (store-update (-> Store Addr Denotable Store))

  (store-update* (-> Store (Listof Addr) (Listof Denotable) Store))

  (store-join (-> Store Store Store)))


main.rkt

'(require/typed/check

  "ui.rkt"

  (analyze (-> Exp MonoStore))

  (format-mono-store (-> MonoStore String)))


structs-adapted.rkt

'(require/typed/check

  "structs.rkt"

  (#:struct Stx ((label : Label)))

  (#:struct (exp Stx) ())

  (#:struct (Ref exp) ((var : Var)))

  (#:struct (Lam exp) ((formals : (Listof Var)) (call : Exp)))

  (#:struct (Call Stx) ((fun : Exp) (args : (Listof Exp)))))


time-adapted.rkt

'(require/typed/check

  "time.rkt"

  (time-zero Time)

  (k (Parameterof Natural))

  (tick (-> Stx Time Time))

  (alloc (-> Time (-> Var Addr))))


ui.rkt

'(require/typed/check

  "ai.rkt"

  (atom-eval (-> BEnv Store (-> Exp Denotable)))

  (next (-> State (Setof State)))

  (explore (-> (Setof State) (Listof State) (Setof State))))


4.2.9 lnm Boundary Types🔗ℹ


lnm-plot.rkt

'(require/typed/check

  "bitstring.rkt"

  (in-reach (-> String Index (Listof String)))

  (log2 (-> Index Index)))


main.rkt

'(require/typed/check

  "lnm-plot.rkt"

  (lnm-plot

   (->

    Summary

    #:L

    (Listof Index)

    #:N

    Index

    #:M

    Index

    #:max-overhead

    Index

    #:cutoff-proportion

    Float

    #:num-samples

    Positive-Integer

    #:plot-height

    Positive-Integer

    #:plot-width

    Positive-Integer

    (Listof Any))))

'(require/typed/check

  "spreadsheet.rkt"

  (rktd->spreadsheet

   (-> Path-String #:output Path-String #:format Symbol Void)))


modulegraph-adapted.rkt

'(require/typed/check

  "modulegraph.rkt"

  (#:struct

   modulegraph

   ((project-name : String) (adjlist : (Listof (Listof String)))))

  (project-name (-> ModuleGraph String))

  (from-tex (-> Path-String ModuleGraph))

  (module-names (-> ModuleGraph (Listof String)))

  (path->project-name (-> Path String)))


spreadsheet.rkt

'(require/typed/check

  "bitstring.rkt"

  (log2 (-> Index Index))

  (natural->bitstring (-> Index #:pad Index String)))


summary-adapted.rkt

'(require/typed/check

  "summary.rkt"

  (#:struct

   summary

   ((source : Path-String)

    (dataset : (Vectorof (Listof Index)))

    (modulegraph : ModuleGraph)))

  (from-rktd (->* (String) (#:graph (U Path #f)) Summary))

  (all-variations (-> Summary (Sequenceof String)))

  (get-num-variations (-> Summary Index))

  (get-project-name (-> Summary String))

  (predicate->variations (-> Summary (-> String Boolean) (Sequenceof String)))

  (untyped-mean (-> Summary Real))

  (variation->mean-runtime (-> Summary String Real)))


summary.rkt

'(require/typed/check

  "bitstring.rkt"

  (bitstring->natural (-> String Index))

  (log2 (-> Index Index))

  (natural->bitstring (-> Index #:pad Index String)))


4.2.10 mbta Boundary Types🔗ℹ


main.rkt

'(require/typed/check "run-t.rkt" (EOM String) (run-t (-> String String)))


run-t.rkt

'(require/typed/check "t-view.rkt" (manage% Manage))


t-view.rkt

'(require/typed/check "t-graph.rkt" (read-t-graph (-> (Instance MBTA))))


4.2.11 morsecode Boundary Types🔗ℹ


main.rkt

'(require/typed/check

  "levenshtein.rkt"

  (string-levenshtein (String String -> Integer)))

'(require/typed/check

  "morse-code-strings.rkt"

  (string->morse (-> String String)))


morse-code-strings.rkt

'(require/typed/check

  "morse-code-table.rkt"

  (char-table (HashTable Char String)))


4.2.12 quadT Boundary Types🔗ℹ


main.rkt

'(require/typed/check "quad-main.rkt" (typeset (-> Quad DocQuad)))

'(require/typed/check "quick-sample.rkt" (quick-sample (-> Quad)))

'(require/typed/check

  "render.rkt"

  (pdf-renderer%

   (Class

    (render-to-file (Quad Path-String -> Void))

    (render-element (Quad -> Any))

    (render-page ((Listof Quad) -> Void))

    (render-word (Quad -> Any))

    (render (-> Quad Any))

    (finalize (-> Any Any))

    (setup (-> Quad Quad)))))

'(require/typed/check

  "world.rkt"

  (world:allow-hyphenated-last-word-in-paragraph Boolean)

  (world:quality-default (Parameterof Index))

  (world:draft-quality Index))


ocm-struct-adapted.rkt

'(require/typed/check

  "ocm-struct.rkt"

  (set-$ocm-tentative! (-> $ocm Index-Type Void))

  (set-$ocm-min-entrys! (-> $ocm (Vectorof Entry-Type) Void))

  (set-$ocm-min-row-indices!

   (-> $ocm (Vectorof (U Index-Type No-Value-Type)) Void))

  (set-$ocm-finished! (-> $ocm Finished-Value-Type Void))

  (set-$ocm-base! (-> $ocm Index-Type Void))

  (#:struct

   $ocm

   ((min-entrys : (Vectorof Entry-Type))

    (min-row-indices : (Vectorof (U Index-Type No-Value-Type)))

    (finished : Finished-Value-Type)

    (matrix-proc : Matrix-Proc-Type)

    (entry->value : Entry->Value-Type)

    (base : Index-Type)

    (tentative : Index-Type))))


penalty-struct-adapted.rkt

'(require/typed/check

  "penalty-struct.rkt"

  (#:struct $penalty ((hyphens : Nonnegative-Integer) (width : Value-Type))))


quad-main.rkt

'(require/typed/check

  "measure.rkt"

  (round-float (-> Float Float))

  (load-text-cache-file (-> Void))

  (update-text-cache-file (-> Void)))

'(require/typed/check

  "quads.rkt"

  (quads->doc (-> (Listof Quad) DocQuad))

  (quads->page (-> (Listof Quad) PageQuad))

  (quads->block (-> (Listof Quad) BlockQuad))

  (quad-attrs (Quad -> QuadAttrs))

  (line

   (->* ((U QuadAttrs HashableList)) () #:rest GroupQuadListItem LineQuad))

  (quad-car (-> Quad QuadListItem))

  (quad-name (-> Quad QuadName))

  (quad-attr-ref

   (->* ((U Quad QuadAttrs) QuadAttrKey) (QuadAttrValue) QuadAttrValue))

  (group-quad-list (GroupQuad -> GroupQuadList))

  (quad-list (Quad -> QuadList))

  (quad-has-attr? (Quad QuadAttrKey -> Boolean))

  (quads->column (-> (Listof Quad) ColumnQuad))

  (page

   (->* ((U QuadAttrs HashableList)) () #:rest GroupQuadListItem PageQuad))

  (column

   (->* ((U QuadAttrs HashableList)) () #:rest GroupQuadListItem ColumnQuad)))

'(require/typed/check

  "sugar-list.rkt"

  (slice-at

   (All

    (A)

    (case->

     ((Listof A) Positive-Integer -> (Listof (Listof A)))

     ((Listof A) Positive-Integer Boolean -> (Listof (Listof A)))))))

'(require/typed/check

  "utils.rkt"

  (merge-attrs (JoinableType * -> QuadAttrs))

  (split-last (All (A) ((Listof A) -> (values (Listof A) A))))

  (join-quads ((Listof Quad) -> (Listof Quad)))

  (hyphenate-quad (QuadListItem -> QuadListItem))

  (quad-map ((QuadListItem -> QuadListItem) Quad -> Quad))

  (group-quad-attr-set* (GroupQuad HashableList -> GroupQuad))

  (quad-attr-set* (Quad HashableList -> Quad))

  (attr-change (-> QuadAttrs HashableList QuadAttrs))

  (compute-line-height (-> Quad Quad))

  (add-vert-positions (-> GroupQuad GroupQuad))

  (split-quad (-> Quad (Listof Quad))))

'(require/typed/check

  "world.rkt"

  (world:line-looseness-key Symbol)

  (world:allow-hyphenated-last-word-in-paragraph Boolean)

  (world:line-looseness-tolerance Float)

  (world:line-index-key Symbol)

  (world:measure-key QuadAttrKey)

  (world:use-hyphenation? Boolean)

  (world:max-quality Index)

  (world:total-lines-key Symbol)

  (world:draft-quality Index)

  (world:quality-key QuadAttrKey)

  (world:quality-key-default (Parameterof Index))

  (world:paper-width-default (Parameterof Float))

  (world:column-count-key QuadAttrKey)

  (world:column-count-key-default (Parameterof Index))

  (world:column-gutter-key QuadAttrKey)

  (world:column-gutter-key-default (Parameterof Float))

  (world:column-index-key QuadAttrKey)

  (world:min-first-lines Index)

  (world:min-last-lines Index)

  (world:minimum-lines-per-column Index)

  (world:default-lines-per-column Index))

'(require/typed/check

  "wrap.rkt"

  (insert-spacers-in-line (->* (LineQuad) ((Option Symbol)) LineQuad))

  (wrap-adaptive (->* ((Listof Quad)) (Float) (Listof LineQuad)))

  (wrap-best (->* ((Listof Quad)) (Float) (Listof LineQuad)))

  (wrap-first (->* ((Listof Quad)) (Float) (Listof LineQuad)))

  (fill (->* (LineQuad) ((Option Float)) LineQuad))

  (add-horiz-positions (-> GroupQuad GroupQuad)))


quick-sample.rkt

'(require/typed/check

  "quads.rkt"

  (page-break (-> Page-BreakQuad))

  (column-break (-> Column-BreakQuad))

  (word (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem WordQuad))

  (box (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem BoxQuad))

  (block (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem BlockQuad))

  (block-break

   (->* ((U HashableList QuadAttrs)) () #:rest QuadListItem Block-BreakQuad)))


render.rkt

'(require/typed/check

  "quads.rkt"

  (quad-attr-ref

   (->* ((U Quad QuadAttrs) QuadAttrKey) (QuadAttrValue) QuadAttrValue))

  (word (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem WordQuad))

  (quad-car (-> Quad QuadListItem))

  (whitespace/nbsp? (-> Any Boolean))

  (quad-name (-> Quad QuadName)))

'(require/typed/check "utils.rkt" (flatten-quad (Quad -> (Listof Quad))))

'(require/typed/check

  "world.rkt"

  (world:font-size-key QuadAttrKey)

  (world:font-size-default (Parameterof Positive-Flonum))

  (world:font-color-key QuadAttrKey)

  (world:font-color-default (Parameterof String))

  (world:font-background-key QuadAttrKey)

  (world:font-background-default (Parameterof String))

  (world:font-name-key QuadAttrKey)

  (world:font-name-default (Parameterof Font-Name))

  (world:font-weight-key QuadAttrKey)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key QuadAttrKey)

  (world:font-style-default (Parameterof Font-Style))

  (world:paper-height-default (Parameterof Float))

  (world:paper-width-default (Parameterof Float))

  (world:x-position-key Symbol)

  (world:y-position-key Symbol)

  (world:ascent-key Symbol)

  (world:quality-default (Parameterof Index))

  (world:draft-quality Index)

  (world:page-key Symbol))


utils.rkt

'(require/typed/check

  "hyphenate.rkt"

  (hyphenate

   (->*

    (String)

    ((U Char String)

     #:exceptions

     (Listof String)

     #:min-length

     Index

     #:min-left-length

     Index

     #:min-right-length

     Index

     #:omit-word

     (-> String Boolean)

     #:omit-string

     (-> String Boolean))

    String)))

'(require/typed/check "measure.rkt" (round-float (-> Float Float)))

'(require/typed/check

  "quads.rkt"

  (word (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem WordQuad))

  (quad-name (-> Quad QuadName))

  (quad-attrs (-> Quad QuadAttrs))

  (make-quadattrs (-> (Listof Any) QuadAttrs))

  (quad-list (Quad -> QuadList))

  (group-quad-list (GroupQuad -> GroupQuadList))

  (box (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem BoxQuad))

  (whitespace/nbsp? (-> Any Boolean))

  (quad-attr-ref

   (->* ((U Quad QuadAttrs) QuadAttrKey) (QuadAttrValue) QuadAttrValue)))

'(require/typed/check

  "world.rkt"

  (world:font-size-key QuadAttrKey)

  (world:font-size-default (Parameterof Positive-Float))

  (world:font-name-key QuadAttrKey)

  (world:font-name-default (Parameterof Font-Name))

  (world:font-weight-key QuadAttrKey)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key QuadAttrKey)

  (world:font-style-default (Parameterof Font-Style))

  (world:mergeable-quad-types (Listof Symbol))

  (world:leading-key QuadAttrKey)

  (world:leading-key-default (Parameterof Float))

  (world:height-key Symbol)

  (world:split-quad-key Symbol)

  (world:x-position-key Symbol)

  (world:y-position-key Symbol))


wrap.rkt

'(require/typed/check

  "measure.rkt"

  (measure-ascent

   (->* (String Font-Size Font-Name) (Font-Weight Font-Style) Float))

  (measure-text (-> String Font-Size Font-Name Font-Weight Font-Style Float))

  (round-float (-> Float Float)))

'(require/typed/check

  "ocm.rkt"

  (make-ocm (->* (Matrix-Proc-Type Entry->Value-Type) (Entry-Type) OCM-Type))

  (ocm-min-index (OCM-Type Index-Type -> (U Index-Type No-Value-Type)))

  (ocm-min-entry (OCM-Type Index-Type -> Entry-Type)))

'(require/typed/check

  "quads.rkt"

  (quads->line (-> (Listof Quad) LineQuad))

  (quad-attrs (-> Quad QuadAttrs))

  (quad-name (Quad -> QuadName))

  (quad-attr-ref

   (->* ((U Quad QuadAttrs) QuadAttrKey) (QuadAttrValue) QuadAttrValue))

  (quad->string (-> Quad String))

  (optical-kern

   (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem Optical-KernQuad))

  (word-break

   (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem Word-BreakQuad))

  (piece

   (->* ((U QuadAttrs HashableList)) () #:rest GroupQuadListItem PieceQuad))

  (line

   (->* ((U QuadAttrs HashableList)) () #:rest GroupQuadListItem LineQuad))

  (whitespace/nbsp? (-> Any Boolean))

  (whitespace? (-> Any Boolean))

  (word-string (-> Quad String))

  (group-quad-list (GroupQuad -> GroupQuadList))

  (quad-list (Quad -> QuadList))

  (spacer (->* ((U QuadAttrs HashableList)) () #:rest QuadListItem SpacerQuad))

  (quad-has-attr? (-> Quad QuadAttrKey Boolean)))

'(require/typed/check

  "sugar-list.rkt"

  (shifts (-> (Listof Quad) (Listof Integer) (Listof (Listof (Option Quad)))))

  (slicef-after (All (A) ((Listof A) (A -> Boolean) -> (Listof (Listof A)))))

  (break-at

   (All

    (A)

    ((Listof A)

     (U Nonnegative-Integer (Listof Nonnegative-Integer))

     ->

     (Listof (Listof A))))))

'(require/typed/check

  "utils.rkt"

  (attr-change (QuadAttrs HashableList -> QuadAttrs))

  (join-quads ((Listof Quad) -> (Listof Quad)))

  (attr-delete (QuadAttrs QuadAttrKey * -> QuadAttrs))

  (split-last (All (A) ((Listof A) -> (values (Listof A) A))))

  (flatten-quadtree ((Treeof Quad) -> (Listof Quad)))

  (merge-attrs (JoinableType * -> QuadAttrs))

  (group-quad-attr-remove* (GroupQuad QuadAttrKey * -> GroupQuad))

  (quad-attr-remove* (Quad QuadAttrKey * -> Quad))

  (quad-attr-set (Quad QuadAttrKey QuadAttrValue -> Quad))

  (group-quad-attr-set (GroupQuad QuadAttrKey QuadAttrValue -> GroupQuad)))

'(require/typed/check

  "world.rkt"

  (world:last-line-can-be-short Boolean)

  (world:new-line-penalty Index)

  (world:hyphen-penalty Index)

  (world:hyphen-limit Index)

  (world:allowed-overfull-ratio Float)

  (world:line-looseness-key Symbol)

  (world:ascent-key Symbol)

  (world:optical-overhang (Parameterof Float))

  (world:hanging-chars (Listof String))

  (world:use-optical-kerns? Boolean)

  (world:before-break-key Symbol)

  (world:default-word-break-list (Parameterof JoinableType))

  (world:no-break-key Symbol)

  (world:word-break-key Symbol)

  (world:spaces (Listof String))

  (world:empty-string String)

  (world:hyphens-and-dashes (Listof String))

  (world:soft-hyphen Char)

  (world:unbreakable-key QuadAttrKey)

  (world:minimum-last-line-chars Index)

  (world:measure-default (Parameterof QuadAttrValue))

  (world:measure-key QuadAttrKey)

  (world:font-size-key QuadAttrKey)

  (world:font-size-default (Parameterof Positive-Flonum))

  (world:font-name-key QuadAttrKey)

  (world:font-name-default (Parameterof Font-Name))

  (world:font-weight-key QuadAttrKey)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key QuadAttrKey)

  (world:font-style-default (Parameterof Font-Style))

  (world:line-index-key QuadAttrKey)

  (world:total-lines-key QuadAttrKey)

  (world:horiz-alignment-last-line-key QuadAttrKey)

  (world:horiz-alignment-key QuadAttrKey)

  (world:horiz-alignment-default (Parameterof QuadAttrKey))

  (world:width-key Symbol)

  (world:x-position-key Symbol)

  (world:y-position-key Symbol))


4.2.13 quadU Boundary Types🔗ℹ


main.rkt

'(require/typed/check "quad-main.rkt" (typeset (-> Quad Quad)))

'(require/typed/check "quick-sample.rkt" (quick-sample (-> Quad)))

'(require/typed/check

  "render.rkt"

  (pdf-renderer%

   (Class

    (render-to-file (Quad Path-String -> Void))

    (render-element (Quad -> Any))

    (render-page ((Listof Quad) -> Void))

    (render-word (Quad -> Any))

    (render (-> Quad Any))

    (finalize (-> Any Any))

    (setup (-> Quad Quad)))))

'(require/typed/check

  "world.rkt"

  (world:allow-hyphenated-last-word-in-paragraph Boolean)

  (world:quality-default (Parameterof Integer))

  (world:draft-quality Index))


ocm-struct-adapted.rkt

'(require/typed/check

  "ocm-struct.rkt"

  (set-$ocm-tentative! (-> $ocm Index-Type Void))

  (set-$ocm-min-entrys! (-> $ocm (Vectorof Entry-Type) Void))

  (set-$ocm-min-row-indices!

   (-> $ocm (Vectorof (U Index-Type No-Value-Type)) Void))

  (set-$ocm-finished! (-> $ocm Finished-Value-Type Void))

  (set-$ocm-base! (-> $ocm Index-Type Void))

  (#:struct

   $ocm

   ((min-entrys : (Vectorof Entry-Type))

    (min-row-indices : (Vectorof (U Index-Type No-Value-Type)))

    (finished : Finished-Value-Type)

    (matrix-proc : Matrix-Proc-Type)

    (entry->value : Entry->Value-Type)

    (base : Index-Type)

    (tentative : Index-Type))))


penalty-struct-adapted.rkt

'(require/typed/check

  "penalty-struct.rkt"

  (#:struct $penalty ((hyphens : Nonnegative-Integer) (width : Value-Type))))


quad-main.rkt

'(require/typed/check

  "../base/csp/csp.rkt"

  (problem%

   (Class

    (init-field (solver Any))

    (field (_solver Any))

    (field (_variable-domains Any))

    (field (_constraints Any))

    (reset (-> Void))

    (custom-print (Output-Port Integer -> Void))

    (custom-display (Output-Port -> Void))

    (custom-write (Output-Port -> Void))

    (add-variable (-> Any (Listof Any) Void))

    (add-variables (-> (Listof Any) Any Void))

    (add-constraint (-> (-> Index Boolean) (Listof Any) Void))

    (get-solution (-> HashTableTop))

    (get-solutions (-> (Listof (HashTable String Integer))))

    (get-solution-iter (-> HashTableTop))

    (set-solver (-> Any Void))

    (get-solver (-> Any)))))

'(require/typed/check

  "measure.rkt"

  (round-float (-> Float Float))

  (load-text-cache-file (-> Void))

  (update-text-cache-file (-> Void)))

'(require/typed/check

  "quads.rkt"

  (make-quadattrs (-> (Listof Any) QuadAttrs))

  (quad-car (-> Quad (U String Quad)))

  (line (->* ((Listof Any)) #:rest USQ Quad))

  (quads->column (-> (Listof Quad) Quad))

  (quads->page (-> (Listof Quad) Quad))

  (quads->block (-> (Listof Quad) Quad))

  (quad-has-attr? (-> Quad Symbol Boolean))

  (quad-name (-> Quad Symbol))

  (quad-attr-ref (->* ((U Quad QuadAttrs) Symbol) (Any) Any))

  (quad-list (-> Quad (Listof USQ)))

  (quad-attrs (-> Quad (Listof Any)))

  (quads->doc (-> (Listof Quad) Quad))

  (page (->* ((Listof Any)) #:rest USQ Quad))

  (column (->* ((Listof Any)) #:rest USQ Quad)))

'(require/typed/check

  "sugar-list.rkt"

  (slice-at

   (All

    (A)

    (case->

     ((Listof A) Positive-Integer -> (Listof (Listof A)))

     ((Listof A) Positive-Integer Boolean -> (Listof (Listof A)))))))

'(require/typed/check

  "utils.rkt"

  (add-vert-positions (-> Quad Quad))

  (attr-change (-> QuadAttrs (Listof Any) QuadAttrs))

  (compute-line-height (-> Quad Quad))

  (hyphenate-quad (USQ -> USQ))

  (join-quads ((Listof Quad) -> (Listof Quad)))

  (merge-attrs (QuadAttrs * -> QuadAttrs))

  (quad-attr-set* (Quad (Listof Any) -> Quad))

  (split-last (All (A) ((Listof A) -> (values (Listof A) A))))

  (split-quad (-> Quad (Listof Quad))))

'(require/typed/check

  "world.rkt"

  (world:line-looseness-key Symbol)

  (world:allow-hyphenated-last-word-in-paragraph Boolean)

  (world:line-looseness-tolerance Float)

  (world:line-index-key Symbol)

  (world:measure-key Symbol)

  (world:use-hyphenation? Boolean)

  (world:max-quality Index)

  (world:total-lines-key Symbol)

  (world:draft-quality Index)

  (world:quality-key Symbol)

  (world:quality-key-default (Parameterof Integer))

  (world:paper-width-default (Parameterof Float))

  (world:column-count-key Symbol)

  (world:column-count-key-default (Parameterof Integer))

  (world:column-gutter-key Symbol)

  (world:column-gutter-key-default (Parameterof Float))

  (world:column-index-key Symbol)

  (world:min-first-lines Index)

  (world:min-last-lines Index)

  (world:minimum-lines-per-column Index)

  (world:default-lines-per-column Index))

'(require/typed/check

  "wrap.rkt"

  (insert-spacers-in-line (->* (Quad) ((Option Symbol)) Quad))

  (wrap-best (->* ((Listof Quad)) (Float) (Listof Quad)))

  (fill (->* (Quad) ((Option Float)) Quad))

  (add-horiz-positions (-> Quad Quad)))


quick-sample.rkt

'(require/typed/check

  "quads.rkt"

  (block (->* (QuadAttrs) #:rest USQ Quad))

  (block-break (-> QuadAttrs Quad))

  (box (->* (QuadAttrs) #:rest USQ Quad))

  (column-break (-> Quad))

  (page-break (-> Quad))

  (word (-> QuadAttrs String Quad)))


render.rkt

'(require/typed/check

  "quads.rkt"

  (quad-attr-ref (->* ((U Quad QuadAttrs) Symbol) (Any) Any))

  (word (->* ((Listof Any)) Quad))

  (quad-name (-> Quad Symbol))

  (quad-car (-> Quad USQ))

  (whitespace/nbsp? (-> Any Boolean)))

'(require/typed/check "utils.rkt" (flatten-quad (-> Quad (Listof Quad))))

'(require/typed/check

  "world.rkt"

  (world:font-size-key Symbol)

  (world:font-size-default (Parameterof Float))

  (world:font-color-key Symbol)

  (world:font-color-default (Parameterof String))

  (world:font-background-key Symbol)

  (world:font-background-default (Parameterof String))

  (world:font-name-key Symbol)

  (world:font-name-default (Parameterof String))

  (world:font-weight-key Symbol)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key Symbol)

  (world:font-style-default (Parameterof Font-Style))

  (world:paper-height-default (Parameterof Float))

  (world:paper-width-default (Parameterof Float))

  (world:x-position-key Symbol)

  (world:y-position-key Symbol)

  (world:ascent-key Symbol)

  (world:quality-default (Parameterof Integer))

  (world:draft-quality Index)

  (world:page-key Symbol))


utils.rkt

'(require/typed/check

  "hyphenate.rkt"

  (hyphenate

   (->*

    (String)

    ((U Char String)

     #:exceptions

     (Listof String)

     #:min-length

     Index

     #:min-left-length

     Index

     #:min-right-length

     Index

     #:omit-word

     (-> String Boolean)

     #:omit-string

     (-> String Boolean))

    String)))

'(require/typed/check "measure.rkt" (round-float (-> Float Float)))

'(require/typed/check

  "quads.rkt"

  (word (-> QuadAttrs String Quad))

  (quad-name (-> Quad Symbol))

  (quad-attrs (-> Quad (Listof Any)))

  (make-quadattrs (-> (Listof Any) QuadAttrs))

  (quad-list (-> Quad (Listof USQ)))

  (box (-> (Listof Any) Quad))

  (quad-attr-ref (->* ((U Quad QuadAttrs) Symbol) (Any) Any))

  (whitespace/nbsp? (-> Any Boolean)))

'(require/typed/check

  "world.rkt"

  (world:font-size-key Symbol)

  (world:font-size-default (Parameterof Float))

  (world:font-name-key Symbol)

  (world:font-name-default (Parameterof String))

  (world:font-weight-key Symbol)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key Symbol)

  (world:font-style-default (Parameterof Font-Style))

  (world:mergeable-quad-types (Listof Symbol))

  (world:leading-key Symbol)

  (world:leading-key-default (Parameterof Float))

  (world:height-key Symbol)

  (world:split-quad-key Symbol)

  (world:x-position-key Symbol)

  (world:y-position-key Symbol))


wrap.rkt

'(require/typed/check

  "measure.rkt"

  (measure-ascent

   (->* (String Positive-Flonum String) (Font-Weight Font-Style) Float))

  (measure-text

   (-> String Positive-Flonum String Font-Weight Font-Style Float))

  (round-float (-> Float Float)))

'(require/typed/check

  "ocm.rkt"

  (make-ocm (->* (Matrix-Proc-Type Entry->Value-Type) (Entry-Type) OCM-Type))

  (ocm-min-index (OCM-Type Index-Type -> (U Index-Type No-Value-Type)))

  (ocm-min-entry (OCM-Type Index-Type -> Entry-Type)))

'(require/typed/check

  "quads.rkt"

  (optical-kern (->* ((Listof Any)) () #:rest USQ Quad))

  (line (->* ((Listof Any)) () #:rest USQ Quad))

  (optical-kern? (-> Any Boolean))

  (piece (->* ((Listof Any)) () #:rest USQ Quad))

  (word-break (->* ((Listof Any)) () #:rest USQ Quad))

  (quad->string (-> Quad String))

  (quad-attr-ref (->* ((U Quad QuadAttrs) Symbol) (Any) Any))

  (quad-attrs (-> Quad (Listof Any)))

  (quad-has-attr? (-> Quad Symbol Boolean))

  (quad-list (Quad -> (Listof USQ)))

  (quad-name (Quad -> Symbol))

  (make-quadattrs (-> (Listof Any) QuadAttrs))

  (quads->line (-> (Listof Quad) Quad))

  (spacer (->* ((Listof Any)) () #:rest USQ Quad))

  (whitespace/nbsp? (-> Any Boolean))

  (whitespace? (-> Any Boolean))

  (word-string (-> Quad String)))

'(require/typed/check

  "sugar-list.rkt"

  (shifts (-> (Listof Quad) (Listof Integer) (Listof (Listof (Option Quad)))))

  (slicef-after (All (A) ((Listof A) (A -> Boolean) -> (Listof (Listof A)))))

  (break-at

   (All

    (A)

    ((Listof A)

     (U Nonnegative-Integer (Listof Nonnegative-Integer))

     ->

     (Listof (Listof A))))))

'(require/typed/check

  "utils.rkt"

  (attr-change (QuadAttrs (Listof Any) -> QuadAttrs))

  (join-quads ((Listof Quad) -> (Listof Quad)))

  (attr-delete (QuadAttrs Symbol * -> QuadAttrs))

  (split-last (All (A) ((Listof A) -> (values (Listof A) A))))

  (flatten-quadtree (QEXP -> (Listof Quad)))

  (merge-attrs (QuadAttrs * -> QuadAttrs))

  (group-quad-attr-remove* (Quad Symbol * -> Quad))

  (quad-attr-remove* (Quad Symbol * -> Quad))

  (quad-attr-set (Quad Symbol Any -> Quad)))

'(require/typed/check

  "world.rkt"

  (world:last-line-can-be-short Boolean)

  (world:new-line-penalty Index)

  (world:hyphen-penalty Index)

  (world:hyphen-limit Index)

  (world:allowed-overfull-ratio Float)

  (world:line-looseness-key Symbol)

  (world:ascent-key Symbol)

  (world:optical-overhang (Parameterof Float))

  (world:hanging-chars (Listof String))

  (world:use-optical-kerns? Boolean)

  (world:before-break-key Symbol)

  (world:default-word-break-list (Parameterof (Listof (U 'bb 'nb String))))

  (world:no-break-key Symbol)

  (world:word-break-key Symbol)

  (world:spaces (Listof String))

  (world:empty-string String)

  (world:hyphens-and-dashes (Listof String))

  (world:soft-hyphen Char)

  (world:unbreakable-key Symbol)

  (world:minimum-last-line-chars Index)

  (world:measure-default (Parameterof Float))

  (world:measure-key Symbol)

  (world:font-size-key Symbol)

  (world:font-size-default (Parameterof Float))

  (world:font-name-key Symbol)

  (world:font-name-default (Parameterof String))

  (world:font-weight-key Symbol)

  (world:font-weight-default (Parameterof Font-Weight))

  (world:font-style-key Symbol)

  (world:font-style-default (Parameterof Font-Style))

  (world:line-index-key Symbol)

  (world:total-lines-key Symbol)

  (world:horiz-alignment-last-line-key Symbol)

  (world:horiz-alignment-key Symbol)

  (world:horiz-alignment-default (Parameterof Symbol))

  (world:width-key Symbol)

  (world:x-position-key Symbol)

  (world:y-position-key Symbol))


4.2.14 sieve Boundary Types🔗ℹ


main.rkt

'(require/typed/check

  "streams.rkt"

  (#:struct stream ((first : Natural) (rest : (-> stream))))

  (make-stream (-> Natural (-> stream) stream))

  (stream-unfold (-> stream (values Natural stream)))

  (stream-get (-> stream Natural Natural))

  (stream-take (-> stream Natural (Listof Natural))))


4.2.15 snake Boundary Types🔗ℹ


collide.rkt

'(require/typed/check "const.rkt" (BOARD-WIDTH Integer) (BOARD-HEIGHT Integer))

'(require/typed/check "data.rkt" (posn=? (-> Posn Posn Boolean)))


data-adaptor.rkt

'(require/typed/check

  "data.rkt"

  (#:struct posn ((x : Real) (y : Real)))

  (#:struct snake ((dir : Dir) (segs : (NEListof Posn))))

  (#:struct world ((snake : Snake) (food : Posn))))


handlers.rkt

'(require/typed/check

  "collide.rkt"

  (snake-wall-collide? (-> Snake Boolean))

  (snake-self-collide? (-> Snake Boolean)))

'(require/typed/check "motion.rkt" (world-change-dir (-> World Dir World)))


main.rkt

'(require/typed/check "const.rkt" (WORLD (-> World)))

'(require/typed/check

  "handlers.rkt"

  (handle-key (-> World String World))

  (game-over? (-> World Boolean)))

'(require/typed/check

  "motion.rkt"

  (reset! (-> Void))

  (world->world (-> World World)))


motion-help.rkt

'(require/typed/check

  "cut-tail.rkt"

  (cut-tail (-> (NEListof Posn) (Listof Posn))))


motion.rkt

'(require/typed/check "const.rkt" (BOARD-WIDTH Integer) (BOARD-HEIGHT Integer))

'(require/typed/check "data.rkt" (posn=? (-> Posn Posn Boolean)))

'(require/typed/check

  "motion-help.rkt"

  (snake-slither (-> Snake Snake))

  (snake-grow (-> Snake Snake)))


4.2.16 suffixtree Boundary Types🔗ℹ


lcs.rkt

'(require/typed/check

  "label.rkt"

  (label->string (-> Label String))

  (string->label (-> String Label))

  (string->label/with-sentinel (-> String Label))

  (make-label (-> (U String (Vectorof (U Char Symbol))) Label))

  (label-source-eq? (-> Label Label Boolean))

  (label-length (-> Label Index))

  (vector->label (-> (Vectorof (U Char Symbol)) Label))

  (label-ref (-> Label Integer (U Symbol Char))))

'(require/typed/check

  "structs.rkt"

  (make-tree (-> Tree))

  (tree-root (-> Tree Node)))

'(require/typed/check "ukkonen.rkt" (tree-add! (-> Tree Label Void)))


main.rkt

'(require/typed/check

  "lcs.rkt"

  (longest-common-substring (-> String String String)))


structs.rkt

'(require/typed/check

  "label.rkt"

  (make-label (-> (U String (Vectorof (U Char Symbol))) Label))

  (label-element-equal? (-> Any Any Boolean))

  (label-length (-> Label Index))

  (label-ref (-> Label Integer (U Symbol Char)))

  (sublabel (case-> (-> Label Index Label) (-> Label Index Index Label)))

  (label-copy (-> Label Label))

  (label-ref-at-end? (-> Label Integer Boolean))

  (label->string (-> Label String))

  (label-source-eq? (-> Label Label Boolean))

  (string->label (-> String Label))

  (string->label/with-sentinel (-> String Label))

  (vector->label (-> (Vectorof (U Char Symbol)) Label))

  (vector->label/with-sentinel (-> (Vectorof Char) Label))

  (label-same-source? (-> Label Label Boolean)))


typed-data.rkt

'(require/typed/check

  "data.rkt"

  (#:struct

   label

   ((datum : (Vectorof (U Char Symbol))) (i : Natural) (j : Natural)))

  (make-label (-> (Vectorof (U Char Symbol)) Natural Natural Label))

  (set-label-i! (-> Label Natural Void))

  (set-label-j! (-> Label Natural Void))

  (#:struct

   node

   ((up-label : Label)

    (parent : (U #f Node))

    (children : (Listof Node))

    (suffix-link : (U #f Node))))

  (make-suffix-tree (-> Node Tree))

  (make-node (-> Label (U #f Node) (Listof Node) (U #f Node) Node))

  (set-node-children! (-> Node (Listof Node) Void))

  (set-node-up-label! (-> Node Label Void))

  (set-node-parent! (-> Node Node Void))

  (set-node-suffix-link! (-> Node Node Void))

  (#:struct suffix-tree ((root : Node))))


ukkonen.rkt

'(require/typed/check

  "label.rkt"

  (label-length (-> Label Index))

  (label-ref (-> Label Integer (U Symbol Char)))

  (label->string (-> Label String))

  (string->label (-> String Label))

  (string->label/with-sentinel (-> String Label))

  (label-element-equal? (-> Any Any Boolean))

  (label-source-eq? (-> Label Label Boolean))

  (vector->label (-> (Vectorof (U Char Symbol)) Label))

  (make-label (-> (U String (Vectorof (U Char Symbol))) Label))

  (sublabel (case-> (-> Label Index Label) (-> Label Index Index Label))))

'(require/typed/check

  "structs.rkt"

  (new-suffix-tree (-> Tree))

  (node-find-child (-> Node Any (U Node #f)))

  (node-root? (-> Node Boolean))

  (node-position-at-end? (-> Node Index Boolean))

  (node-add-leaf! (-> Node Label Node))

  (node-up-splice-leaf! (-> Node Index Label (values Node Node)))

  (node-follow/k

   (->

    Node

    Label

    (-> Node (Pairof Node Index))

    (-> Node Index (Pairof Node Index))

    (-> Node Label Index (Pairof Node Index))

    (-> Node Index Label Index (Pairof Node Index))

    (Pairof Node Index))))


4.2.17 synth Boundary Types🔗ℹ


array-broadcast.rkt

'(require/typed/check

  "array-struct.rkt"

  (array-strict? (-> Array Boolean))

  (array-default-strict! (-> Array Void))

  (array-shape (-> Array Indexes))

  (array-size (-> Array Integer))

  (unsafe-array-proc (-> Array (-> Indexes Float)))

  (unsafe-build-array (-> Indexes (-> Indexes Float) Array)))

'(require/typed/check

  "array-utils.rkt"

  (make-thread-local-indexes (-> Integer (-> Indexes))))


array-struct.rkt

'(require/typed/check

  "array-utils.rkt"

  (unsafe-array-index->value-index (-> Indexes Indexes Integer))

  (check-array-shape-size (-> Symbol Indexes Integer))

  (check-array-shape (-> (Vectorof Integer) (-> Nothing) Indexes)))


array-transform.rkt

'(require/typed/check

  "array-broadcast.rkt"

  (array-broadcast (-> Array Indexes Array))

  (array-shape-broadcast (-> (Listof Indexes) Indexes)))

'(require/typed/check

  "array-struct.rkt"

  (array-shape (-> Array Indexes))

  (unsafe-array-proc (-> Array (-> Indexes Float)))

  (array-default-strict! (-> Array Void))

  (unsafe-build-array (-> Indexes (-> Indexes Float) Array)))

'(require/typed/check

  "array-utils.rkt"

  (unsafe-vector-remove (-> Indexes Integer Indexes))

  (vector-copy-all (-> Indexes Indexes))

  (unsafe-vector-insert (-> Indexes Integer Integer Indexes)))


drum.rkt

'(require/typed/check

  "array-struct.rkt"

  (array-size (-> Array Integer))

  (make-array (-> In-Indexes Flonum Array))

  (build-array (-> In-Indexes (-> Indexes Float) Array))

  (unsafe-vector->array (-> Indexes (Vectorof Float) Mutable-Array)))

'(require/typed/check

  "array-transform.rkt"

  (array-append* ((Listof Array) -> Array)))

'(require/typed/check

  "array-utils.rkt"

  (array-shape-size (-> Indexes Integer))

  (check-array-shape (-> In-Indexes (-> Nothing) Indexes)))

'(require/typed/check

  "synth.rkt"

  (fs Natural)

  (seconds->samples (-> Float Integer)))


main.rkt

'(require/typed/check "drum.rkt" (drum (-> Natural Pattern Natural Array)))

'(require/typed/check "mixer.rkt" (mix (-> Weighted-Signal * Array)))

'(require/typed/check

  "sequencer.rkt"

  (note (-> Symbol Natural Natural (Pairof Natural Natural)))

  (sequence

   (->

    Natural

    (Listof (Pairof (U Natural #f) Natural))

    Natural

    (-> Float (-> Indexes Float))

    Array)))

'(require/typed/check

  "synth.rkt"

  (emit (-> Array (Vectorof Integer)))

  (sawtooth-wave (-> Float (-> Indexes Float))))


mixer.rkt

'(require/typed/check

  "array-broadcast.rkt"

  (array-broadcast (-> Array Indexes Array))

  (array-shape-broadcast

   (case->

    ((Listof Indexes) -> Indexes)

    ((Listof Indexes) (U #f #t 'permissive) -> Indexes)))

  (array-broadcasting (Parameterof (U #f #t 'permissive))))

'(require/typed/check

  "array-struct.rkt"

  (array? (-> Array Boolean))

  (array-shape (-> Array Indexes))

  (array-default-strict! (-> Array Void))

  (unsafe-array-proc (-> Array (-> Indexes Float)))

  (unsafe-build-array (-> Indexes (-> Indexes Float) Array)))


sequencer.rkt

'(require/typed/check

  "array-struct.rkt"

  (build-array (-> Indexes (-> Indexes Flonum) Array)))

'(require/typed/check

  "array-transform.rkt"

  (array-append* ((Listof Array) -> Array)))

'(require/typed/check "mixer.rkt" (mix (-> Weighted-Signal * Array)))

'(require/typed/check "synth.rkt" (fs Natural))


synth.rkt

'(require/typed/check

  "array-struct.rkt"

  (array? (-> Array Boolean))

  (array-shape (-> Array Indexes))

  (unsafe-array-proc (-> Array (-> Indexes Float)))

  (array-size (-> Array Integer))

  (array-strictness (Parameterof (U #f #t))))

'(require/typed/check

  "array-utils.rkt"

  (next-indexes! (-> Indexes Integer Indexes Void)))


typed-data.rkt

'(require/typed/check

  "data.rkt"

  (#:struct

   Array

   ((shape : Indexes)

    (size : Integer)

    (strict? : (Boxof Boolean))

    (strict! : (-> Void))

    (unsafe-proc : (-> Indexes Float))))

  (#:struct (Settable-Array Array) ((set-proc : (Indexes Float -> Void))))

  (#:struct (Mutable-Array Settable-Array) ((data : (Vectorof Float)))))


4.2.18 take5 Boundary Types🔗ℹ


card-adapted.rkt

'(require/typed/check

  "card.rkt"

  (#:struct card ((face : Face) (bulls : Bulls)))

  (>-face (-> Card Card Boolean))

  (--face (-> Card Card Natural)))


card-pool.rkt

'(require/typed/check

  "basics.rkt"

  (FACE Natural)

  (HAND Natural)

  (MIN-BULL Natural)

  (MAX-BULL Natural))


dealer.rkt

'(require/typed/check

  "basics.rkt"

  (FACE Natural)

  (FIVE Natural)

  (STACKS Natural)

  (SIXTYSIX Natural)

  (HAND Natural)

  (MIN-BULL Bulls)

  (MAX-BULL Bulls)

  (configuration (-> (Listof (List Symbol Natural)))))

'(require/typed/check

  "card-pool.rkt"

  (create-card-pool (-> (-> (Listof Card) (Listof Card)) (-> Bulls) CardPool)))

'(require/typed/check "deck.rkt" (create-deck (-> CardPool Deck)))

'(require/typed/check "player.rkt" (player% Player%))


deck.rkt

'(require/typed/check "basics.rkt" (FACE Natural) (STACKS Natural))

'(require/typed/check "stack.rkt" (bulls (-> Stack Natural)))


main.rkt

'(require/typed/check "dealer.rkt" (create-dealer (-> (Listof Player) Dealer)))

'(require/typed/check "player.rkt" (create-player (-> Natural Player)))


4.2.19 tetris Boundary Types🔗ℹ


aux.rkt

'(require/typed/check

  "tetras.rkt"

  (build-tetra-blocks

   (-> Color Real Real Real Real Real Real Real Real Real Real Tetra)))


base-types.rkt

'(require/typed/check

  "data.rkt"

  (#:struct posn ((x : Real) (y : Real)))

  (#:struct block ((x : Real) (y : Real) (color : Color)))

  (#:struct tetra ((center : posn) (blocks : (Listof Block))))

  (#:struct world ((tetra : tetra) (blocks : (Listof Block)))))


block.rkt

'(require/typed/check "data.rkt" (posn=? (-> Posn Posn Boolean)))


bset.rkt

'(require/typed/check

  "block.rkt"

  (block-rotate-ccw (-> Posn Block Block))

  (block-rotate-cw (-> Posn Block Block))

  (block=? (-> Block Block Boolean))

  (block-move (-> Real Real Block Block)))

'(require/typed/check "consts.rkt" (board-width Integer))


elim.rkt

'(require/typed/check

  "bset.rkt"

  (blocks-move (-> Real Real BSet BSet))

  (full-row? (-> BSet Natural Boolean))

  (blocks-union (-> BSet BSet BSet))

  (blocks-row (-> BSet Real BSet)))

'(require/typed/check "consts.rkt" (board-height Integer))


main.rkt

'(require/typed/check

  "aux.rkt"

  (list-pick-random (-> (Listof Tetra) Tetra))

  (tetras (Listof Tetra)))

'(require/typed/check "bset.rkt" (blocks-overflow? (-> BSet Boolean)))

'(require/typed/check

  "world.rkt"

  (world-key-move (-> World String World))

  (next-world (-> World World)))


tetras.rkt

'(require/typed/check

  "bset.rkt"

  (blocks-intersect (-> BSet BSet BSet))

  (blocks-move (-> Real Real BSet BSet))

  (blocks-rotate-cw (-> Posn BSet BSet))

  (blocks-rotate-ccw (-> Posn BSet BSet))

  (blocks-change-color (-> BSet Color BSet)))


world.rkt

'(require/typed/check

  "aux.rkt"

  (list-pick-random (-> (Listof Tetra) Tetra))

  (neg-1 Negative-Fixnum)

  (tetras (Listof Tetra)))

'(require/typed/check

  "bset.rkt"

  (blocks-union (-> BSet BSet BSet))

  (blocks-max-x (-> BSet Real))

  (blocks-min-x (-> BSet Real))

  (blocks-max-y (-> BSet Real)))

'(require/typed/check

  "consts.rkt"

  (board-height Integer)

  (board-width Integer))

'(require/typed/check "elim.rkt" (eliminate-full-rows (-> BSet BSet)))

'(require/typed/check

  "tetras.rkt"

  (tetra-move (-> Real Real Tetra Tetra))

  (tetra-rotate-ccw (-> Tetra Tetra))

  (tetra-rotate-cw (-> Tetra Tetra))

  (tetra-overlaps-blocks? (-> Tetra BSet Boolean))

  (tetra-change-color (-> Tetra Color Tetra)))


4.2.20 zombie Boundary Types🔗ℹ


image-adapted.rkt

'(require/typed/check

  "image.rkt"

  (#:struct image ((impl : Any)))

  (empty-scene (-> Real Real Image))

  (place-image (-> Image Real Real Image Image))

  (circle (-> Real String String Image)))


main.rkt

'(require/typed/check

  "zombie.rkt"

  (w0 World)

  (world-on-mouse (-> World (-> Real Real String World)))

  (world-on-tick (-> World (-> World))))


zombie.rkt

'(require/typed/check

  "math.rkt"

  (min (-> Real Real Real))

  (max (-> Real Real Real))

  (abs (-> Real Real))

  (sqr (-> Real Real))

  (msqrt (-> Real Real)))


4.2.21 zordoz Boundary Types🔗ℹ


main.rkt

'(require/typed/check

  "zo-shell.rkt"

  (zo-read (-> Path-String zo))

  (init (-> (Vector zo String) Void)))


zo-find.rkt

'(require/typed/check "zo-string.rkt" (zo->spec (-> zo Spec)))

'(require/typed/check

  "zo-transition.rkt"

  (zo-transition (-> zo String (values (U zo (Listof zo)) Boolean))))


zo-shell.rkt

'(require/typed/check

  "zo-find.rkt"

  (zo-find (-> zo String (#:limit (U Natural #f)) (Listof result)))

  (#:struct result ((zo : zo) (path : (Listof zo)))))

'(require/typed/check

  "zo-string.rkt"

  (zo->spec (-> zo Spec))

  (zo->string (->* (zo) (#:deep? Boolean) String)))

'(require/typed/check

  "zo-transition.rkt"

  (zo-transition (-> zo String (values (U zo (Listof zo)) Boolean))))


5 Dynamic Benchmark Details🔗ℹ

This section reports low-level details about the execution of the theoretical worst-case configuration (for short: TWC) of each benchmark. The TWC configuration is the one in which every boundary between migratable modules is guarded by a contract. In Typed Racket terms, this means every import between migratable modules is via require/typed. (This configuration has worse performance than any configuration that combines typed and untyped modules — because in those real configurations, only some of the boundaries are guarded with contracts.)

The data in this section was obtained by running a version of Racket v6.12 instrumented with compiler-level counters to track chaperone use. The patch implementing the counters is part of this repository’s source code, and is adapted from a patch by Strickland, Tobin–Hochstadt, Findler, and Flatt (2012).

5.1 Time and Garbage Collection Details🔗ℹ

The data in figure 2 comes from calling vector-set-performance-stats! after running the TWC configuration. Column Milliseconds column reports total running time (including setup, i.e., reading from data files) in milliseconds. Column GC Milliseconds column reports the total garbage collection time. Column Num. GC reports the number of garbage collections performed since start-up in the current place. Column Peak Bytes reports the largest number of bytes that were allocated just before a garbage collection.

Benchmark

  

Milliseconds

  

GC Milliseconds

  

Num. GC

  

Peak Bytes

acquire

  

6,293

  

1,587

  

139

  

146,894,440

dungeon

  

70,666

  

3,589

  

2,149

  

147,577,704

forth

  

74,813

  

15,507

  

677

  

303,901,560

fsm

  

2,589,549

  

94

  

16

  

77,190,296

fsmoo

  

86,403

  

19,645

  

1,885

  

152,493,328

gregor

  

729

  

95

  

25

  

80,615,000

jpeg

  

1,049

  

106

  

32

  

83,640,840

kcfa

  

6,193

  

250

  

189

  

120,089,088

lnm

  

5,423

  

1,042

  

62

  

259,078,516

mbta

  

1,449

  

119

  

39

  

88,572,704

morsecode

  

2,986

  

108

  

77

  

76,856,896

quadT

  

4,569

  

237

  

51

  

137,533,784

quadU

  

6,096

  

400

  

89

  

161,384,976

sieve

  

13,083

  

2,181

  

600

  

126,061,064

snake

  

8,939

  

125

  

239

  

80,043,536

suffixtree

  

79,443

  

225

  

745

  

91,639,328

synth

  

22,013

  

1,529

  

746

  

118,585,360

take5

  

253

  

57

  

15

  

53,035,776

tetris

  

8,539

  

130

  

344

  

79,435,848

zombie

  

138,849

  

6,589

  

1,556

  

1,465,774,984

zordoz

  

5,506

  

117

  

132

  

86,678,600

Figure 2: TWC Time Details

5.2 Chaperones Details🔗ℹ

The data in figure 3 reports low-level details about chaperones.

Quick reference:

In more detail: Proc. apps counts the number of times the benchmark applies a chapereoned procedure, Struct apps counts the number of field references or property accesses to chaperoned structs, and Vec. apps counts the number of references to chaperoned vectors. The Proc. makes, Struct makes, and Vec. makes columns count the number of times each kind of chaperone was created. Finally, Proc. depth, Struct depth, and Vec. depth report the largest number of chaperones layered on top of one value. For example, if Proc. depth is 3 then there is at least one function in the benchmark that gets wrapped in three procedure chaperones when the benchmark runs.

Benchmark

  

Proc. apps

  

Proc. makes

  

Proc. depth

acquire

  

39,524

  

380,246

  

2

dungeon

  

831,105

  

11,921,217

  

2

forth

  

6,275

  

6,429

  

42

fsm

  

1,005

  

1,153

  

0

fsmoo

  

639,703

  

7,044,372

  

2

gregor

  

211

  

402

  

2

jpeg

  

24

  

198

  

0

kcfa

  

3,584

  

1,608

  

0

lnm

  

1,907

  

3,309

  

2

mbta

  

498,808

  

67,936

  

2

morsecode

  

3

  

151

  

0

quadT

  

62,546

  

5,654

  

3

quadU

  

40,329

  

5,654

  

3

sieve

  

5

  

156

  

0

snake

  

11,739,420

  

171

  

0

suffixtree

  

3,935,912

  

194,900

  

2

synth

  

30,332,598

  

982

  

3

take5

  

1

  

185

  

2

tetris

  

5,071

  

192

  

0

zombie

  

28,087,410

  

28,162,362

  

749

zordoz

  

572,191

  

644,109

  

2

Benchmark

  

Struct apps

  

Struct makes

  

Struct depth

acquire

  

1,598,182

  

33,956

  

3

dungeon

  

5,611,400

  

931,438

  

2

forth

  

964,418

  

85,130

  

3

fsm

  

2,500

  

42

  

2

fsmoo

  

4,345,592

  

418,746

  

3

gregor

  

180

  

57

  

2

jpeg

  

2

  

40

  

2

kcfa

  

0

  

38

  

2

lnm

  

26,464

  

360

  

2

mbta

  

949,872

  

49

  

2

morsecode

  

0

  

38

  

2

quadT

  

239,023

  

179,465

  

391

quadU

  

231,904

  

172,426

  

391

sieve

  

0

  

38

  

2

snake

  

0

  

38

  

2

suffixtree

  

0

  

38

  

2

synth

  

0

  

38

  

2

take5

  

0

  

38

  

2

tetris

  

0

  

38

  

2

zombie

  

0

  

38

  

2

zordoz

  

14,437,179

  

8,580

  

2

Benchmark

  

Vec. apps

  

Vec. makes

  

Vec. depth

acquire

  

0

  

0

  

0

dungeon

  

1,221,200

  

1,008,400

  

2

forth

  

0

  

0

  

0

fsm

  

1,098,376,908

  

5,002

  

2,001

fsmoo

  

4,766,800

  

2,506,770

  

3

gregor

  

116,980

  

29,009

  

2

jpeg

  

5,434,754

  

1,271,986

  

3

kcfa

  

0

  

0

  

0

lnm

  

331,756

  

7

  

2

mbta

  

0

  

0

  

0

morsecode

  

0

  

0

  

0

quadT

  

249,124

  

15,580

  

24

quadU

  

243,004

  

12,932

  

24

sieve

  

0

  

0

  

0

snake

  

0

  

0

  

0

suffixtree

  

108,592

  

48,672

  

0

synth

  

72,673,976

  

40,215,654

  

15

take5

  

0

  

0

  

0

tetris

  

0

  

0

  

0

zombie

  

0

  

0

  

0

zordoz

  

88

  

67

  

0

Figure 3: TWC Chaperone Details

6 Reproducibility🔗ℹ

When rebuilding this document, subscribe to the gtp-benchmarks logger for information about the build:

PLTSTDERR="error info@gtp-benchmarks" raco setup gtp-benchmarks

6.1 Module Dependence Graphs🔗ℹ

Script for generate module dependence graphs.

procedure

(make-modulegraph src*)  modulegraph?

  src* : (listof path-string?)
Create an adjacency list of require depedencies between the given modules. Uses module->imports to collect dependencies.

procedure

(modulegraph? x)  boolean?

  x : any/c
Predicate for an adjacency list.

procedure

(complete-path->imported-modules p)  (listof complete-path?)

  p : path-string?
Uses module->imports to build a list of one file’s imports.

Added in version 5.1 of package gtp-benchmarks.

procedure

(complete-path->exported-identifiers p)  (listof symbol?)

  p : path-string?
Uses module->exports to collect the names of one file’s exports.

Added in version 5.1 of package gtp-benchmarks.

6.2 Size Information🔗ℹ

Script for counting size and dependencies.

procedure

(benchmark-size-info name)  hash?

  name : symbol?
Count size statistics for a benchmark. Return a hash of labeled values.

Example:
> (benchmark-size-info 'zordoz)

'#hash(("# Bnd." . 6)

       ("# Exp." . 11)

       ("# Modules" . 5)

       ("Annotation LOC" . 225)

       ("Untyped LOC" . 1392))

Added in version 9.2.1 of package gtp-benchmarks.

6.3 Type Information🔗ℹ

Script for collecting the types in a benchmark

procedure

(compile/require-typed-check-info src)  (listof string?)

  src : path-string?
Compiles the given module, returns all log messages generated by the require-typed-check-logger.

6.4 Counting Chaperones🔗ℹ

Script for collecting low-level performance details. This script requires a version of Racket patched with special performance counters. There is a (possibly out-of-date) copy of the patch included with this repository.

procedure

(count-chaperones bin src)  chaperones-count/c

  bin : racket-bin/count-chaperones?
  src : path-string?
Invokes the raco executable in the given binary folder to compile the given module, then uses the racket executable in bin to run src. Collects performance info using vector-set-performance-stats! and the performance counters installed by the patch mentioned above.

procedure

(racket-bin/count-chaperones? x)  boolean?

  x : any/c
Returns true for a directory that contains raco and racket executables with support for counting chaperones.

contract

chaperones-count/c

 : (hash/c symbol? (or/c natural? hash?) #:immutable #true #:flat? #true)
Predicate for the performance info generated by the count-chaperones function.

Bibliography🔗ℹ

[REP-2023] Ben Greenman, “GTP Benchmarks for Gradual Typing Performance,” 1st ACM Conference on Reproducibility and Replicability, 2023. https://doi.org/10.1145/3589806.3600034
[JFP-2019] Ben Greenman and Asumu Takikawa and Max S. New and Daniel Feltey and Robert Bruce Findler and Jan Vitek and Matthias Felleisen, “How to evaluate the performance of gradual type systems,” Journal of Functional Programming, 2019. https://www.cambridge.org/core/journals/journal-of-functional-programming/article/how-to-evaluate-the-performance-of-gradual-type-systems/DC765724C52A3A462F16C7FB3AD18697

Summarizes the evaluation method; introduces the GTP benchmarks.

[PEPM-2018] Ben Greenman and Zeina Migeed, “On the Cost of Type-Tag Soundness,” Workshop on Partial Evaluation and Program Manipulation, 2018. https://www2.ccs.neu.edu/racket/pubs/pepm18-gm.pdf

Generalizes the evaluation method for a study of Reticulated Python. Introduces a method to approximate the number of good configurations in a mixed-typed program [blog post].

[POPL-2016] Asumu Takikawa and Daniel Feltey and Ben Greenman and Max S. New and Jan Vitek and Matthias Felleisen, “Is Sound Gradual Typing Dead?,” Symposium on Principles of Programming Languages, 2016. https://www2.ccs.neu.edu/racket/pubs/popl16-tfgnvf.pdf

Introduces a method to evaluate the performance of a gradual typing system and applies the method to Typed Racket.

[OAAM] J. Ian Johnson, Nicholas Labich, Matthew Might, and David Van Horn, “Optimizing Abstract Abstract Machines,” International Conference on Functional Programming, 2015. https://dl.acm.org/citation.cfm?id=2500604
[CFA2] Dimitrios Vardoulakis and Olin Shivers, “CFA2: a Context-Free approach to Control-Flow analysis,” European Symposium on Programming, 2011. https://link.springer.com/content/pdf/10.1007%2F978-3-642-11957-6_30.pdf