GTP Benchmarks
1 Running a benchmark
make-configurations
2 Benchmark Descriptions
2.1 acquire Description
2.2 dungeon Description
2.3 forth Description
2.4 fsm Description
2.5 gregor Description
2.6 jpeg Description
2.7 kcfa Description
2.8 lnm Description
2.9 mbta Description
2.10 morsecode Description
2.11 quad  BG Description
2.12 quad  MB Description
2.13 sieve Description
2.14 snake Description
2.15 suffixtree Description
2.16 synth Description
2.17 take5 Description
2.18 tetris Description
2.19 zombie Description
2.20 zordoz Description
3 Static Benchmark Details
3.1 Benchmark Size
3.2 Benchmark Types
3.2.1 acquire Boundary Types
3.2.2 dungeon Boundary Types
3.2.3 forth Boundary Types
3.2.4 fsm Boundary Types
3.2.5 fsmoo Boundary Types
3.2.6 gregor Boundary Types
3.2.7 jpeg Boundary Types
3.2.8 kcfa Boundary Types
3.2.9 lnm Boundary Types
3.2.10 mbta Boundary Types
3.2.11 morsecode Boundary Types
3.2.12 quad  BG Boundary Types
3.2.13 quad  MB Boundary Types
3.2.14 sieve Boundary Types
3.2.15 snake Boundary Types
3.2.16 suffixtree Boundary Types
3.2.17 synth Boundary Types
3.2.18 take5 Boundary Types
3.2.19 tetris Boundary Types
3.2.20 zombie Boundary Types
3.2.21 zordoz Boundary Types
4 Dynamic Benchmark Details
4.1 Time and Garbage Collection Details
4.2 Chaperones Details
5 Reproducibility
5.1 Module Dependence Graphs
make-modulegraph
modulegraph?
5.2 Type Information
compile/  require-typed-check-info
5.3 Counting Chaperones
count-chaperones
racket-bin/  count-chaperones?
chaperones-count/  c
7.1

GTP Benchmarks

GTP = gradual typing performance

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

This package contains benchmarks for measuring the cost of typed/untyped interaction in Typed Racket.

1 Running a benchmark

To run a benchmark:

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.

On the command-line:

racket utilities/make-configurations.rkt benchmarks/NAME

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

2.1 acquire Description


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

0. admin.rkt

  

3. board.rkt

  

6. state.rkt

  

9. ../base/untyped.rkt

1. auxiliaries.rkt

  

4. main.rkt

  

7. strategy.rkt

  

2. basics.rkt

  

5. player.rkt

  

8. tree.rkt

  

2.2 dungeon Description


author: Vincent St-Amour
source: ?
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

2.3 forth Description


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

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

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


image

0. command.rkt

  

1. eval.rkt

  

2. main.rkt

  

3. stack.rkt

2.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.
image

0. automata.rkt

  

1. main.rkt

  

2. population.rkt

  

3. utilities.rkt

2.5 gregor Description


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

0. clock.rkt

  

4. difference.rkt

  

8. moment-base.rkt

  

12. ymd.rkt

1. core-structs.rkt

  

5. gregor-structs.rkt

  

9. moment.rkt

  

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

2. date.rkt

  

6. hmsn.rkt

  

10. offset-resolvers.rkt

  

3. datetime.rkt

  

7. main.rkt

  

11. time.rkt

  

2.6 jpeg Description


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

0. bit-ports.rkt

  

2. huffman.rkt

  

4. main.rkt

1. exif.rkt

  

3. jfif.rkt

  

5. ../base/untyped.rkt

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

0. ai.rkt

  

2. denotable.rkt

  

4. structs.rkt

  

6. ui.rkt

1. benv.rkt

  

3. main.rkt

  

5. time.rkt

  

2.8 lnm Description


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

0. bitstring.rkt

  

2. main.rkt

  

4. spreadsheet.rkt

1. lnm-plot.rkt

  

3. modulegraph.rkt

  

5. summary.rkt

2.9 mbta Description


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

0. main.rkt

  

2. t-graph.rkt

  

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

1. run-t.rkt

  

3. t-view.rkt

  

2.10 morsecode Description


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

0. levenshtein.rkt

  

1. main.rkt

  

2. morse-code-strings.rkt

  

3. morse-code-table.rkt

2.11 quadBG Description


author: Ben Greenman
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format. This benchmark is similar to the quadMB benchmark except for its choice of type annotations; the types that quadBG uses to describe its input correspond to flat contracts.
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

2.12 quadMB Description


author: Matthew Butterick
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format (same as quadBG). This benchmark performs slightly different computations in its typed and untyped versions: the typed version uses recursive predicates (derived from its types) to guide control flow, whereas the untyped version uses flat predicates.
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/core.rkt

3. ocm-struct.rkt

  

7. quads.rkt

  

11. utils.rkt

  

15. ../base/csp/csp.rkt

2.13 sieve Description


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

0. main.rkt

  

1. streams.rkt

2.14 snake Description


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

0. collide.rkt

  

2. cut-tail.rkt

  

4. handlers.rkt

  

6. motion-help.rkt

1. const.rkt

  

3. data.rkt

  

5. main.rkt

  

7. motion.rkt

2.15 suffixtree Description


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

0. data.rkt

  

2. lcs.rkt

  

4. structs.rkt

1. label.rkt

  

3. main.rkt

  

5. ukkonen.rkt

2.16 synth Description


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

0. array-broadcast.rkt

  

3. array-utils.rkt

  

6. main.rkt

  

9. synth.rkt

1. array-struct.rkt

  

4. data.rkt

  

7. mixer.rkt

  

2. array-transform.rkt

  

5. drum.rkt

  

8. sequencer.rkt

  

2.17 take5 Description


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

0. basics.rkt

  

3. dealer.rkt

  

6. player.rkt

1. card-pool.rkt

  

4. deck.rkt

  

7. stack.rkt

2. card.rkt

  

5. main.rkt

  

8. ../base/untyped.rkt

2.18 tetris Description


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

0. aux.rkt

  

3. consts.rkt

  

6. main.rkt

1. block.rkt

  

4. data.rkt

  

7. tetras.rkt

2. bset.rkt

  

5. elim.rkt

  

8. world.rkt

2.19 zombie Description


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

0. image.rkt

  

1. main.rkt

  

2. math.rkt

  

3. zombie.rkt

2.20 zordoz Description


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

0. main.rkt

  

2. zo-shell.rkt

  

4. zo-transition.rkt

  

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

1. zo-find.rkt

  

3. zo-string.rkt

  

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

  

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

3 Static Benchmark Details

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

quadBG

  

6779

  

221

  

14

  

27

  

160

quadMB

  

6700

  

292

  

14

  

27

  

172

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.

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

3.2.1 acquire Boundary Types


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

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


basics.rkt

'(require/typed/check

  "auxiliaries.rkt"

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


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

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


main.rkt

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


tree.rkt

'(require/typed/check

  "basics.rkt"

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

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


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


player.rkt

'(require/typed/check

  "admin.rkt"

  (administrator% Administrator%)

  (turn% Turn%))


strategy.rkt

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


3.2.2 dungeon Boundary Types


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


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


3.2.3 forth Boundary Types


main.rkt

'(require/typed/check

  "eval.rkt"

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


eval.rkt

'(require/typed/check

  "command.rkt"

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

  (command% Command%))


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


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


population.rkt

'(require/typed/check

  "utilities.rkt"

  (choose-randomly

   (->

    (Listof Probability)

    Natural

    (#:random (U False Real))

    (Listof Natural))))


3.2.5 fsmoo Boundary Types


automata-adapted.rkt

'(require/typed/check

  "automata.rkt"

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


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


main.rkt

'(require/typed/check

  "utilities.rkt"

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


3.2.6 gregor Boundary Types


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


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

  "date.rkt"

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

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

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


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


time.rkt

'(require/typed/check

  "hmsn.rkt"

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

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

  (NS/SECOND Natural))


datetime.rkt

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


moment.rkt

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


moment-base.rkt

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


offset-resolvers.rkt

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


clock.rkt

'(require/typed/check

  "moment.rkt"

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

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

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

  (UTC String)

  (moment

   (->*

    (Natural)

    (Month

     Natural

     Natural

     Natural

     Natural

     Natural

     #:tz

     (U tz #f)

     #:resolve-offset

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

    Moment))

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

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

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


difference.rkt

'(require/typed/check

  "ymd.rkt"

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


3.2.7 jpeg Boundary Types


main.rkt

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


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


huffman.rkt

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


3.2.8 kcfa Boundary Types


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


main.rkt

'(require/typed/check

  "ui.rkt"

  (analyze (-> Exp MonoStore))

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


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


time-adapted.rkt

'(require/typed/check

  "time.rkt"

  (time-zero Time)

  (k (Parameterof Natural))

  (tick (-> Stx Time Time))

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


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


ui.rkt

'(require/typed/check

  "ai.rkt"

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

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

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


3.2.9 lnm Boundary Types


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


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


main.rkt

'(require/typed/check

  "spreadsheet.rkt"

  (rktd->spreadsheet

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


spreadsheet.rkt

'(require/typed/check

  "bitstring.rkt"

  (log2 (-> Index Index))

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


lnm-plot.rkt

'(require/typed/check

  "bitstring.rkt"

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

  (log2 (-> Index Index)))


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


3.2.11 morsecode Boundary Types


main.rkt

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


3.2.12 quadBG Boundary Types


main.rkt

'(require/typed/check

  "world.rkt"

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

  (world:quality-default (Parameterof Integer))

  (world:draft-quality Index))


quad-main.rkt

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


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


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


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


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

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


3.2.13 quadMB Boundary Types


main.rkt

'(require/typed/check

  "world.rkt"

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

  (world:quality-default (Parameterof Index))

  (world:draft-quality Index))


quad-main.rkt

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


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


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


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


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

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


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


3.2.15 snake Boundary Types


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


main.rkt

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


motion.rkt

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


motion-help.rkt

'(require/typed/check

  "cut-tail.rkt"

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


handlers.rkt

'(require/typed/check

  "collide.rkt"

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

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


collide.rkt

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


3.2.16 suffixtree Boundary Types


main.rkt

'(require/typed/check

  "lcs.rkt"

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


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


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


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


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


3.2.17 synth Boundary Types


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


main.rkt

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


sequencer.rkt

'(require/typed/check

  "array-struct.rkt"

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


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-struct.rkt"

  (array-shape (-> Array Indexes))

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

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

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


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


synth.rkt

'(require/typed/check

  "array-utils.rkt"

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


mixer.rkt

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


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


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


main.rkt

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


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


card-pool.rkt

'(require/typed/check

  "basics.rkt"

  (FACE Natural)

  (HAND Natural)

  (MIN-BULL Natural)

  (MAX-BULL Natural))


deck.rkt

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


3.2.19 tetris Boundary Types


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


main.rkt

'(require/typed/check

  "aux.rkt"

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

  (tetras (Listof Tetra)))


aux.rkt

'(require/typed/check

  "tetras.rkt"

  (build-tetra-blocks

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


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


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


block.rkt

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


world.rkt

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


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


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


3.2.21 zordoz Boundary Types


main.rkt

'(require/typed/check

  "zo-shell.rkt"

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

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


zo-shell.rkt

'(require/typed/check

  "zo-string.rkt"

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

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


zo-find.rkt

'(require/typed/check

  "zo-transition.rkt"

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


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

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

quadBG

  

6,096

  

400

  

89

  

161,384,976

quadMB

  

4,486

  

194

  

51

  

137,390,608

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

4.2 Chaperones Details

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

Quick reference:

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

Benchmark

  

Proc. apps

  

Proc. makes

  

Proc. depth

acquire

  

39,524

  

380,246

  

2

dungeon

  

831,105

  

11,921,217

  

2

forth

  

6,275

  

6,429

  

42

fsm

  

1,005

  

1,153

  

0

fsmoo

  

639,703

  

7,044,372

  

2

gregor

  

211

  

402

  

2

jpeg

  

24

  

198

  

0

kcfa

  

3,584

  

1,608

  

0

lnm

  

1,907

  

3,309

  

2

mbta

  

498,808

  

67,936

  

2

morsecode

  

3

  

151

  

0

quadBG

  

40,329

  

5,654

  

3

quadMB

  

62,546

  

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

quadBG

  

231,904

  

172,426

  

391

quadMB

  

239,023

  

179,465

  

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

quadBG

  

243,004

  

12,932

  

24

quadMB

  

249,124

  

15,580

  

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

5 Reproducibility

5.1 Module Dependence Graphs

Script for generate module dependence graphs.

procedure

(make-modulegraph src*)  modulegraph?

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

procedure

(modulegraph? x)  boolean?

  x : any/c
Predicate for an adjacency list.

5.2 Type Information

Script for collecting the types in a benchmark

procedure

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

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

5.3 Counting Chaperones

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

procedure

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

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

procedure

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

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

contract

chaperones-count/c

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