GTP Benchmarks

8.16.0.1

GTP Benchmarks🔗ℹ

GTP = gradual typing performance

Latest Version: 9.3

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.

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🔗ℹ

Create a new directory relative to the benchmark’s "base/" folder (if it exists)
Copy the benchmark’s "both/" folder into the new directory
Copy your favorite mix of "typed/" and "untyped/" modules into the new directory
Run the "main.rkt" module

1.2 Official Route🔗ℹ

Install the gtp-measure package
Make a copy of the sample benchmarking script in this repo and modify it to match your machine / goals.
Run via:
PLTSTDERR="error info@gtp-measure" raco gtp-measure --output sample-data/ sample-gtp-measure-manifest.rkt

1.3 Semi-Auto Route🔗ℹ

On the command-line:
racket utilities/make-configurations.rkt benchmarks/NAME
This creates a directory with all typed/untyped configurations.
Move to a configuration sub-directory and run the "main.rkt" module.

(require gtp-benchmarks/utilities/make-configurations)
	package: gtp-benchmarks

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

Changed in version 9.3: Change a require/typed declaration in morsecode from Index to Integer to match the exporting module. (057039).
Changed in version 9.2: Add an assert in take5 to accommodate the improved type of random in Racket v8.9 (246173a67). This change affects the typed and untyped configurations.
Changed in version 9.1: In take5, replace the (module+ main expr) with the unwrapped expression expr. This matches the structure of other benchmarks and makes it easier to run tools like the statistical profiler documentation and the contract profiler documentation, which do not check submodules by default.
Changed in version 9.0: Substantially revise acquire and take5. Before, acquire ran a game with AI players that all raised exceptions and take5 ignored an input list of AI players. After, the acquire players make valid moves and take5 uses its input. These changes have little impact on typed/untyped overhead.
Changed in version 8.0: Remove racket/sandbox dependency from acquire and change the benchmark to stop using a player AI that times out. Timing info from sandbox depends on system calls; measurements should be more stable without it. Based on a first measurement, the typed/untyped overhead in acquire is the same before and after.
Changed in version 7.0: Fix a typed/untyped mismatch in lnm; both versions of a certain helper function return (void) now.
Changed in version 6.0: Major Release. Edited all benchmarks to match up typed and untyped code. Typed code now uses assert instead of cast and untyped code uses an untyped version of the same predicate function. Reordered functions / methods so that a per-file diff lines up; the only differences between files now should be types and require forms. After, lnm has lower overhead because of new asserts in untyped code. Both quadU and quadT have higher overhead, possibly because Typed Racket fixed a soundness hole in the meantime (1643443).
Changed in version 5.0: (1) Remove an unused call to format in the typed version of zordoz. This change significantly improves the runtime of typed code; for example, the typed/untyped ratio improves by an order of magnitude.
(2) Fix an unbound identifier error in the typed version of lnm. This error went undiscovered because the plot library caught and ignored it, but does not change overall performance.
Changed in version 4.0: Replace a high-cost cast in zombie with a predicate, and use the same predicate in untyped code. This change makes the benchmark a better test for "the cost of mixing typed and untyped code" by removing an un-equal computation between the untyped and typed versions. (It would be good to reduce the run-time cost of casts, but that’s not the main concern of this benchmark suite.)
Changed in version 3.0: Fixed an issue in the untyped zordoz code. Before, the untyped code imported the typed version of the compiler/zo-structs library. After, the untyped code avoids this unnecessary type boundary. This issue seriously affects the conclusion about zordoz reached in [JFP-2019]. That paper compares one version of zordoz that does not suffer the issue (6.2) against two that do (6.3 and 6.4), and incorrectly concludes that changes to Typed Racket improved the overhead in the later versions. In fact, the overhead is better because the untyped code got unnecessarily slower. More at: https://github.com/bennn/gtp-benchmarks/issues/16.
Changed in version 2.0: Fixed a difference between the typed and untyped mbta code. Before, untyped created a function (curry argmax f). After, both create a function (lambda (l) ((curry argmax f) l)).
Changed in version 1.0: Renamed quadBG to quadU and replaced quadMB with quadT. In the beginning, quad came to us as two programs: an original untyped program and a fully-typed version by the original author. The quadMB benchmark integrated these two programs; this was a BAD decision, because the typed version performed significantly different computations due to uses of cast and define-predicate. The quadBG benchmark added types to the untyped program (with minimal changes to the code). The new quadMB benchmark removes types from the typed program (with minimal changes to the code). Please do not refer to quadBG or quadMB in future applications of this benchmark suite.

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.

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.

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).

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.

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.

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.

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]).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

#: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

#: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:

Proc. = procedure chaperone
Struct = struct chaperone
Vec = vector chaperone
apps = applications and reads
makes = allocations
depth = layers of chaperones

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🔗ℹ

(require gtp-benchmarks/utilities/modulegraph)
	package: gtp-benchmarks

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🔗ℹ

(require gtp-benchmarks/utilities/size-info)
	package: gtp-benchmarks

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🔗ℹ

(require gtp-benchmarks/utilities/type-info)
	package: gtp-benchmarks

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🔗ℹ

(require gtp-benchmarks/utilities/count-chaperones)
	package: gtp-benchmarks

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

1	Running a benchmark
2	Version Notes
3	Benchmark Descriptions
4	Static Benchmark Details
5	Dynamic Benchmark Details
6	Reproducibility
	Bibliography

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

0. cell.rkt		2. main.rkt		4. utils.rkt
1. grid.rkt		3. message-queue.rkt		5. ../base/un-types.rkt

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

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

0. ai.rkt		2. denotable.rkt		4. structs.rkt		6. ui.rkt
1. benv.rkt		3. main.rkt		5. time.rkt

0. bitstring.rkt		2. main.rkt		4. spreadsheet.rkt
1. lnm-plot.rkt		3. modulegraph.rkt		5. summary.rkt

0. main.rkt		2. t-graph.rkt		4. ../base/my-graph.rkt
1. run-t.rkt		3. t-view.rkt

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

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

0. data.rkt		2. lcs.rkt		4. structs.rkt
1. label.rkt		3. main.rkt		5. ukkonen.rkt

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

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

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

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

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

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

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