Create a new directory next to the benchmark’s "base/" folder. (From inside the newly-created directory, the path "../base/" must work, if a "base" folder exists.)
Copy the contents of the benchmark’s "both/" directory (if it exists) into the new directory.
Copy your favorite mix of "typed/" and "untyped/" modules into the new directory
Run the "main.rkt" module

Typed benchmark files probably require the package require-typed-check. You can either install it, or manually edit all uses to either require/typed (if the required module is untyped) or require (if the required module is typed) as appropriate.

1.2Official Route🔗 i

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.3Semi-Auto Route🔗 i

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

2Version Notes🔗 i

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

3Benchmark Descriptions🔗 i

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.1acquire Description🔗 i

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.2dungeon Description🔗 i

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.3forth Description🔗 i

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.4fsm Description🔗 i

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.5gregor Description🔗 i

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.6jpeg Description🔗 i

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.7kcfa Description🔗 i

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.8lnm Description🔗 i

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.9mbta Description🔗 i

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.10morsecode Description🔗 i

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.11quadU Description🔗 i

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.12quadT Description🔗 i

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.13sieve Description🔗 i

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.14snake Description🔗 i

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.15suffixtree Description🔗 i

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.16synth Description🔗 i

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.17take5 Description🔗 i

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.18tetris Description🔗 i

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.19zombie Description🔗 i

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.20zordoz Description🔗 i

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

4Static Benchmark Details🔗 i

4.1Benchmark Size🔗 i

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.2Benchmark Types🔗 i

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.1acquire Boundary Types🔗 i

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.2dungeon Boundary Types🔗 i

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.3forth Boundary Types🔗 i

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.4fsm Boundary Types🔗 i

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.5fsmoo Boundary Types🔗 i

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.6gregor Boundary Types🔗 i

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.7jpeg Boundary Types🔗 i

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.8kcfa Boundary Types🔗 i

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.9lnm Boundary Types🔗 i

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.10mbta Boundary Types🔗 i

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.11morsecode Boundary Types🔗 i

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.12quadT Boundary Types🔗 i

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.13quadU Boundary Types🔗 i

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.14sieve Boundary Types🔗 i

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.15snake Boundary Types🔗 i

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.16suffixtree Boundary Types🔗 i

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.17synth Boundary Types🔗 i

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.18take5 Boundary Types🔗 i

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.19tetris Boundary Types🔗 i

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.20zombie Boundary Types🔗 i

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.21zordoz Boundary Types🔗 i

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

5Dynamic Benchmark Details🔗 i

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.1Time and Garbage Collection Details🔗 i

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.2Chaperones Details🔗 i

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

6Reproducibility🔗 i

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.1Module Dependence Graphs🔗 i

(require gtp-benchmarks/utilities/modulegraph )

package: gtp-benchmarks

Script for generate module dependence graphs.

procedure
( make-modulegraphsrc*)→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-modulesp)→(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-identifiersp)→(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.2Size Information🔗 i

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

package: gtp-benchmarks

Script for counting size and dependencies.

procedure
( benchmark-size-infoname)→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.3Type Information🔗 i

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

package: gtp-benchmarks

Script for collecting the types in a benchmark

procedure
( compile/require-typed-check-infosrc)→(listof string? )
src:path-string?

Compiles the given module, returns all log messages generated by the require-typed-check-logger .

6.4Counting Chaperones🔗 i

(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 binsrc)→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🔗 i

[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

top ← prev up next →