GTP Benchmarks
GTP = gradual typing performance
Latest Version: 5.2
Source: https://github.com/bennn/gtp-benchmarks
This package contains benchmarks for measuring the cost of typed/untyped interaction in Typed Racket.
Always include a version number when reporting data on these benchmarks.
1 Running a benchmark
Three options:
1.1 Quick Route
Create a new directory relative to the benchmark’s "base/" folder (if it exists)
Copy the benchmark’s "both/" folder into the new directory
Copy your favorite mix of "typed/" and "untyped/" modules into the new directory
Run the "main.rkt" module
1.2 Official Route
Install the gtp-measure package
Make a copy of the sample benchmarking script in this repo and modify it to match your machine / goals.
- Run via:
PLTSTDERR="error info@gtp-measure" raco gtp-measure --output sample-data/ sample-gtp-measure-manifest.rkt
1.3 Semi-Auto Route
- On the command-line:
racket utilities/make-configurations.rkt benchmarks/NAME
This creates a directory with all typed/untyped configurations. Move to a configuration sub-directory and run the "main.rkt" module.
procedure
(make-configurations dir) → void?
dir : (and/c path-string? directory-exists?)
2 Version Notes
See also the GitHub release notes: https://github.com/bennn/gtp-benchmarks/releases
Changed in version 5.0: (1) Remove an unused call to format in the typed version of zordoz. This change significantly improves the runtime of typed code; for example, the typed/untyped ratio improves by an order of magnitude.
(2) Fix an unbound identifier error in the typed version of lnm. This error went undiscovered because the plot library caught and ignored it, but does not change overall performance.Changed in version 4.0: Replace a high-cost cast in zombie with a predicate, and use the same predicate in untyped code. This change makes the benchmark a better test for "the cost of mixing typed and untyped code" by removing an un-equal computation between the untyped and typed versions. (It would be good to reduce the run-time cost of casts, but that’s not the main concern of this benchmark suite.)
Changed in version 3.0: Fixed an issue in the untyped zordoz code. Before, the untyped code imported the typed version of the compiler/zo-structs library. After, the untyped code avoids this unnecessary type boundary. This issue seriously affects the conclusion about zordoz reached in [JFP-2019]. That paper compares one version of zordoz that does not suffer the issue (6.2) against two that do (6.3 and 6.4), and incorrectly concludes that changes to Typed Racket improved the overhead in the later versions. In fact, the overhead is better because the untyped code got unnecessarily slower. More at: https://github.com/bennn/gtp-benchmarks/issues/16.
Changed in version 2.0: Fixed a difference between the typed and untyped mbta code. Before, untyped created a function (curry argmax f). After, both create a function (lambda (l) ((curry argmax f) l)).
Changed in version 1.0: Renamed quadBG to quadU and replaced quadMB with quadT. In the beginning, quad came to us as two programs: an original untyped program and a fully-typed version by the original author. The quadMB benchmark integrated these two programs; this was a BAD decision, because the typed version performed significantly different computations due to uses of cast and define-predicate. The quadBG benchmark added types to the untyped program (with minimal changes to the code). The new quadMB benchmark removes types from the typed program (with minimal changes to the code). Please do not refer to quadBG or quadMB in future applications of this benchmark suite.
3 Benchmark Descriptions
This section has summaries of the benchmark programs.
In each description, the author and source fields credit the authors of the code that inspired the benchmarks. The dependencies field lists any libraries outside the core of Racket and Typed Racket that the benchmarks use; we assume that programmers who use gradual typing cannot change the language of these libraries (the libraries are either typed or untyped).
Each benchmark comes with a short description of its behavior,
a module dependence graph,
and the names of its migratable and fixed modules.
In the module graphs, edges point from one module to another whenever one
module requires another.
Nodes for migratable modules are circles —
Note: these graphs do not show type adaptor modules.
3.1 acquire Description
author: Matthias Felleisen
source: github.com/mfelleisen/Acquire
dependencies: None
Simulates a board game between player objects. The players send messages to an administrator object; the administrator enforces the rules of the game.
0. admin.rkt
3. board.rkt
6. state.rkt
9. ../base/untyped.rkt
1. auxiliaries.rkt
4. main.rkt
7. strategy.rkt
2. basics.rkt
5. player.rkt
8. tree.rkt
3.2 dungeon Description
author: Vincent St-Amour
source: ?
dependencies: None
Builds a maze of wall and floor objects by drawing first-class classes from a list.
0. cell.rkt
2. main.rkt
4. utils.rkt
1. grid.rkt
3. message-queue.rkt
5. ../base/un-types.rkt
3.3 forth Description
author: Ben Greenman
source: github.com/bennn/forth
dependencies: None
Interprets Forth programs.
The interpreter represents calculator commands as a list of first-class objects.
Note: this benchmark runs very quickly untyped (< 50 milliseconds), and extremely slowly with certain type boundaries. As the extreme slowdowns improve, we plan to increase the input size so the untyped configuration runs in the 1-2 second range.
Changed in version 0.2: Increased input size, thanks to Typed Racket improvements (ff2956d).
0. command.rkt
1. eval.rkt
2. main.rkt
3. stack.rkt
3.4 fsm Description
author: Linh Chi Nguyen
source: github.com/ayaderaghul/sample-fsm
dependencies: None
Simulates an economy with finite-state automata. The economy is implemented as a vector; this vector repeatedly crosses between modules in the benchmark.
0. automata.rkt
1. main.rkt
2. population.rkt
3. utilities.rkt
3.5 gregor Description
author: Jon Zeppieri
source: github.com/97jaz/gregor
dependencies: cldr (untyped) and tzinfo (untyped)
Provides tools for manipulating calendar dates. The benchmark builds tens of date values and runs unit tests on these values.
0. clock.rkt
4. difference.rkt
8. moment-base.rkt
12. ymd.rkt
1. core-structs.rkt
5. gregor-structs.rkt
9. moment.rkt
13. ../base/tzinfo/main.rkt
2. date.rkt
6. hmsn.rkt
10. offset-resolvers.rkt
3. datetime.rkt
7. main.rkt
11. time.rkt
3.6 jpeg Description
author: Andy Wingo
source: github.com/wingo/racket-jpeg
dependencies: math/array (typed) and rnrs/bytevectors-6 (untyped)
Parses a bytestream of JPEG data to an internal representation, then serializes the result.
0. bit-ports.rkt
2. huffman.rkt
4. main.rkt
6. ../base/untyped.rkt
1. exif.rkt
3. jfif.rkt
5. ../base/math/array.rkt
3.7 kcfa Description
author: Matt Might
source: matt.might.net/articles/implementation-of-kcfa-and-0cfa/
dependencies: None
Performs 2-CFA on a lambda calculus equation built from Church numerals; specifically, it analyzes an encoding of (2 * (1 + 3)) = (1 * 2) (provided by Dee Glaze via [OAAM] (church-num) via [CFA2]).
0. ai.rkt
2. denotable.rkt
4. structs.rkt
6. ui.rkt
1. benv.rkt
3. main.rkt
5. time.rkt
3.8 lnm Description
author: Ben Greenman
source: github.com/nuprl/gradual-typing-performance/tree/master/paper/popl-2016/scripts
dependencies: plot (typed) and math/statistics (typed)
Renders a plot and spreadsheet for some gradual typing data. Two modules in this benchmark are tightly-coupled to Typed Racket libraries; typing both modules improves performance.
0. bitstring.rkt
2. main.rkt
4. spreadsheet.rkt
1. lnm-plot.rkt
3. modulegraph.rkt
5. summary.rkt
3.9 mbta Description
author: Matthias Felleisen
source: ?
dependencies: graph (untyped)
Builds a map of Boston’s subway system and answers reachability queries. The map encapsulates a boundary to Racket’s untyped graph library; when the map is typed, the boundary to graph is a performance bottleneck.
0. main.rkt
2. t-graph.rkt
4. ../base/my-graph.rkt
1. run-t.rkt
3. t-view.rkt
3.10 morsecode Description
authors: John B. Clements and Neil Van Dyke
source: github.com/jbclements/morse-code-trainer/tree/master/morse-code-trainer
dependencies: None
Computes Levenshtein distances and morse code translations for a sequence of pairs of words.
0. levenshtein.rkt
1. main.rkt
2. morse-code-strings.rkt
3. morse-code-table.rkt
3.11 quadU Description
author: Ben Greenman
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format. This benchmark started from an untyped program by the original author. For the benchmark, we added types with minimal changes to the code.
0. hyphenate.rkt
4. ocm.rkt
8. quick-sample.rkt
12. world.rkt
1. main.rkt
5. penalty-struct.rkt
9. render.rkt
13. wrap.rkt
2. measure.rkt
6. quad-main.rkt
10. sugar-list.rkt
14. ../base/csp/csp.rkt
3. ocm-struct.rkt
7. quads.rkt
11. utils.rkt
15. ../base/quad-types.rkt
3.12 quadT Description
author: Matthew Butterick
source: github.com/mbutterick/quad
dependencies: csp (untyped)
Converts S-expression source code to PDF format. This benchmark started from a typed program by the original author. For the benchmark, we removed types with minimal changes to the code. Any cast forms changed to analogous contract forms, and any define-predicate forms changed to functions or contracts.
0. hyphenate.rkt
5. penalty-struct.rkt
10. sugar-list.rkt
15. ../base/untyped-predicates.rkt
1. main.rkt
6. quad-main.rkt
11. utils.rkt
16. ../base/untyped.rkt
2. measure.rkt
7. quads.rkt
12. world.rkt
3. ocm-struct.rkt
8. quick-sample.rkt
13. wrap.rkt
4. ocm.rkt
9. render.rkt
14. ../base/csp/csp.rkt
3.13 sieve Description
author: Ben Greenman
source: github.com/nuprl/gradual-typing-performance/tree/master/benchmarks/sieve
dependencies: None
Computes prime numbers using a stream library.
0. main.rkt
1. streams.rkt
3.14 snake Description
author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Functional program that implements the Snake game. The benchmark folds over a sequence of game moves.
0. collide.rkt
2. cut-tail.rkt
4. handlers.rkt
6. motion-help.rkt
1. const.rkt
3. data.rkt
5. main.rkt
7. motion.rkt
3.15 suffixtree Description
author: Danny Yoo
source: github.com/dyoo/suffixtree
dependencies: None
Computes longest common subsequences between strings.
0. data.rkt
2. lcs.rkt
4. structs.rkt
1. label.rkt
3. main.rkt
5. ukkonen.rkt
3.16 synth Description
author: Vincent St. Amour & Neil Toronto
source: github.com/stamourv/synth
dependencies: None
Converts a description of notes and drum beats to WAV format. This benchmark creates a large number of vectors (to represent notes) but rarely reads from the vectors.
0. array-broadcast.rkt
3. array-utils.rkt
6. main.rkt
9. synth.rkt
1. array-struct.rkt
4. data.rkt
7. mixer.rkt
2. array-transform.rkt
5. drum.rkt
8. sequencer.rkt
3.17 take5 Description
author: Matthias Felleisen
source: github.com/mfelleisen/take5
dependencies: None
Simulates a card game between player objects. The players communicate through a dealer object.
0. basics.rkt
3. dealer.rkt
6. player.rkt
1. card-pool.rkt
4. deck.rkt
7. stack.rkt
2. card.rkt
5. main.rkt
8. ../base/untyped.rkt
3.18 tetris Description
author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Functional implementation of Tetris; the benchmark replays a pre-recorded sequence of moves.
0. aux.rkt
3. consts.rkt
6. main.rkt
1. block.rkt
4. data.rkt
7. tetras.rkt
2. bset.rkt
5. elim.rkt
8. world.rkt
3.19 zombie Description
author: David Van Horn
source: github.com/philnguyen/soft-contract
dependencies: None
Implements a game where players avoid enemies. This benchmark uses an encoding of objects as higher-order functions to implement the game player, the enemies, and the board.
0. image.rkt
1. main.rkt
2. math.rkt
3. zombie.rkt
3.20 zordoz Description
author: Ben Greenman
source: github.com/bennn/zordoz
dependencies: compiler/zo-parse (untyped) and compiler/zo-structs (untyped)
Traverses Racket bytecode (.zo files). The compiler library defines the bytecode data structures.
0. main.rkt
2. zo-shell.rkt
4. zo-transition.rkt
6. ../base/compiler-zo-structs.rkt
1. zo-find.rkt
3. zo-string.rkt
5. ../base/compiler-zo-parse.rkt
7. ../base/typed-zo-structs.rkt
4 Static Benchmark Details
4.1 Benchmark Size
Benchmark
Untyped LOC
Annotation LOC
# Modules
# Bnd.
# Exp.
acquire
1654
304
9
26
106
dungeon
541
69
5
5
38
forth
257
31
4
4
10
fsm
182
56
4
5
17
fsmoo
194
83
4
4
9
gregor
945
175
13
42
142
jpeg
1432
165
5
5
50
kcfa
230
53
7
17
62
lnm
488
114
6
8
28
mbta
266
71
4
3
8
morsecode
159
38
4
3
15
quadT
6685
307
14
27
174
quadU
6779
221
14
27
160
sieve
35
17
2
1
9
snake
159
50
8
16
31
suffixtree
537
130
6
11
69
synth
837
138
10
26
51
take5
318
34
8
14
26
tetris
249
107
9
23
58
zombie
300
25
4
3
15
zordoz
1393
223
5
6
12
The table in figure 1 quantifies the benchmarks’ size and structure. The Untyped LOC column lists the number of non-whitespace, non-comment lines of code in the untyped version of each benchmark (computed by the syntax-sloc library). The Annotation LOC is the additional number of lines in the typed version of each benchmark; this estimates the number of type annotations in the typed version. The # Modules column is the number of modules in each benchmark, and lastly the # Bnd. and # Exp. columns summarize the dependencies between these modules. One boundary (counted in # Bnd.) is one import statement from one module in the benchmark to another. One export (counted in # Exp.) is one identifier provided by one module in the benchmark.
4.2 Benchmark Types
This section contains the source code for each boundary between modules in the benchmarks. The data format is:
benchmark name
importing module
'(require-typed-check exporting-module ...)
In other words, the data below shows the require/typed/check forms for each module in each benchmark.
Depending on the configuration, a require/typed/check expands to either a require or a require/typed form. The latter form compiles types to contracts; these contracts are the reason why some configurations run slower than others. In this way, the types below give an idea of the kind of overhead each benchmark may suffer from.
Note: the data below may refer to type aliases. See the source code for each benchmark to find what the aliases stand for.
4.2.1 acquire Boundary Types
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))) |
4.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%)) |
4.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))) |
4.2.4 fsm Boundary Types
main.rkt
'(require/typed/check |
"population.rkt" |
(build-random-population (-> Natural Population)) |
(population-payoffs (-> Population (Listof Payoff))) |
(death-birth (-> Population Natural (#:random (U False Real)) Population)) |
(match-up* (-> Population Natural Population))) |
population.rkt
'(require/typed/check |
"utilities.rkt" |
(choose-randomly |
(-> |
(Listof Probability) |
Natural |
(#:random (U False Real)) |
(Listof Natural)))) |
4.2.5 fsmoo Boundary Types
automata-adapted.rkt
'(require/typed/check |
"automata.rkt" |
(make-random-automaton (-> Natural oAutomaton))) |
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))) |
4.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)))) |
4.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))) |
4.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)))) |
4.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))) |
4.2.10 mbta Boundary Types
main.rkt
'(require/typed/check "run-t.rkt" (EOM String) (run-t (-> String String))) |
run-t.rkt
'(require/typed/check "t-view.rkt" (manage% Manage)) |
t-view.rkt
'(require/typed/check "t-graph.rkt" (read-t-graph (-> (Instance MBTA)))) |
4.2.11 morsecode Boundary Types
main.rkt
'(require/typed/check |
"morse-code-strings.rkt" |
(string->morse (-> String String))) |
morse-code-strings.rkt
'(require/typed/check |
"morse-code-table.rkt" |
(char-table (HashTable Char String))) |
4.2.12 quadT Boundary Types
main.rkt
'(require/typed/check |
"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)) |
4.2.13 quadU 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)) |
4.2.14 sieve Boundary Types
main.rkt
'(require/typed/check |
"streams.rkt" |
(#:struct stream ((first : Natural) (rest : (-> stream)))) |
(make-stream (-> Natural (-> stream) stream)) |
(stream-unfold (-> stream (values Natural stream))) |
(stream-get (-> stream Natural Natural)) |
(stream-take (-> stream Natural (Listof Natural)))) |
4.2.15 snake Boundary Types
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)) |
4.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)))) |
4.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))) |
4.2.18 take5 Boundary Types
card-adapted.rkt
'(require/typed/check |
"card.rkt" |
(#:struct card ((face : Face) (bulls : Bulls))) |
(>-face (-> Card Card Boolean)) |
(--face (-> Card Card Natural))) |
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)) |
4.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))) |
4.2.20 zombie Boundary Types
image-adapted.rkt
'(require/typed/check |
"image.rkt" |
(#:struct image ((impl : Any))) |
(empty-scene (-> Real Real Image)) |
(place-image (-> Image Real Real Image Image)) |
(circle (-> Real String String Image))) |
main.rkt
'(require/typed/check |
"zombie.rkt" |
(w0 World) |
(world-on-mouse (-> World (-> Real Real String World))) |
(world-on-tick (-> World (-> World)))) |
zombie.rkt
'(require/typed/check |
"math.rkt" |
(min (-> Real Real Real)) |
(max (-> Real Real Real)) |
(abs (-> Real Real)) |
(sqr (-> Real Real)) |
(msqrt (-> Real Real))) |
4.2.21 zordoz Boundary Types
main.rkt
'(require/typed/check |
"zo-shell.rkt" |
(zo-read (-> Path-String zo)) |
(init (-> (Vector zo String) Void))) |
zo-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)))) |
5 Dynamic Benchmark Details
This section reports low-level details about the execution of the
theoretical worst-case configuration (for short: TWC) of each benchmark.
The TWC configuration is the one in which every boundary between
migratable modules is guarded by a contract.
In Typed Racket terms, this means every import between migratable modules is
via require/typed.
(This configuration has worse performance than any configuration that
combines typed and untyped modules —
The data in this section was obtained by running a version of Racket v6.12 instrumented with compiler-level counters to track chaperone use. The patch implementing the counters is part of this repository’s source code, and is adapted from a patch by Strickland, Tobin-Hochstadt, Findler, and Flatt (2012).
5.1 Time and Garbage Collection Details
The data in figure 2 comes from calling vector-set-performance-stats! after running the TWC configuration. Column Milliseconds column reports total running time (including setup, i.e., reading from data files) in milliseconds. Column GC Milliseconds column reports the total garbage collection time. Column Num. GC reports the number of garbage collections performed since start-up in the current place. Column Peak Bytes reports the largest number of bytes that were allocated just before a garbage collection.
Benchmark
Milliseconds
GC Milliseconds
Num. GC
Peak Bytes
acquire
6,293
1,587
139
146,894,440
dungeon
70,666
3,589
2,149
147,577,704
forth
74,813
15,507
677
303,901,560
fsm
2,589,549
94
16
77,190,296
fsmoo
86,403
19,645
1,885
152,493,328
gregor
729
95
25
80,615,000
jpeg
1,049
106
32
83,640,840
kcfa
6,193
250
189
120,089,088
lnm
5,423
1,042
62
259,078,516
mbta
1,449
119
39
88,572,704
morsecode
2,986
108
77
76,856,896
quadT
4,569
237
51
137,533,784
quadU
6,096
400
89
161,384,976
sieve
13,083
2,181
600
126,061,064
snake
8,939
125
239
80,043,536
suffixtree
79,443
225
745
91,639,328
synth
22,013
1,529
746
118,585,360
take5
253
57
15
53,035,776
tetris
8,539
130
344
79,435,848
zombie
138,849
6,589
1,556
1,465,774,984
zordoz
5,506
117
132
86,678,600
Figure 2: TWC Time Details
5.2 Chaperones Details
The data in figure 3 reports low-level details about chaperones.
Quick reference:
Proc. = procedure chaperone
Struct = struct chaperone
Vec = vector chaperone
apps = applications and reads
makes = allocations
depth = layers of chaperones
In more detail: Proc. apps counts the number of times the benchmark applies a chapereoned procedure, Struct apps counts the number of field references or property accesses to chaperoned structs, and Vec. apps counts the number of references to chaperoned vectors. The Proc. makes, Struct makes, and Vec. makes columns count the number of times each kind of chaperone was created. Finally, Proc. depth, Struct depth, and Vec. depth report the largest number of chaperones layered on top of one value. For example, if Proc. depth is 3 then there is at least one function in the benchmark that gets wrapped in three procedure chaperones when the benchmark runs.
Benchmark
Proc. apps
Proc. makes
Proc. depth
acquire
39,524
380,246
2
dungeon
831,105
11,921,217
2
forth
6,275
6,429
42
fsm
1,005
1,153
0
fsmoo
639,703
7,044,372
2
gregor
211
402
2
jpeg
24
198
0
kcfa
3,584
1,608
0
lnm
1,907
3,309
2
mbta
498,808
67,936
2
morsecode
3
151
0
quadT
62,546
5,654
3
quadU
40,329
5,654
3
sieve
5
156
0
snake
11,739,420
171
0
suffixtree
3,935,912
194,900
2
synth
30,332,598
982
3
take5
1
185
2
tetris
5,071
192
0
zombie
28,087,410
28,162,362
749
zordoz
572,191
644,109
2
Benchmark
Struct apps
Struct makes
Struct depth
acquire
1,598,182
33,956
3
dungeon
5,611,400
931,438
2
forth
964,418
85,130
3
fsm
2,500
42
2
fsmoo
4,345,592
418,746
3
gregor
180
57
2
jpeg
2
40
2
kcfa
0
38
2
lnm
26,464
360
2
mbta
949,872
49
2
morsecode
0
38
2
quadT
239,023
179,465
391
quadU
231,904
172,426
391
sieve
0
38
2
snake
0
38
2
suffixtree
0
38
2
synth
0
38
2
take5
0
38
2
tetris
0
38
2
zombie
0
38
2
zordoz
14,437,179
8,580
2
Benchmark
Vec. apps
Vec. makes
Vec. depth
acquire
0
0
0
dungeon
1,221,200
1,008,400
2
forth
0
0
0
fsm
1,098,376,908
5,002
2,001
fsmoo
4,766,800
2,506,770
3
gregor
116,980
29,009
2
jpeg
5,434,754
1,271,986
3
kcfa
0
0
0
lnm
331,756
7
2
mbta
0
0
0
morsecode
0
0
0
quadT
249,124
15,580
24
quadU
243,004
12,932
24
sieve
0
0
0
snake
0
0
0
suffixtree
108,592
48,672
0
synth
72,673,976
40,215,654
15
take5
0
0
0
tetris
0
0
0
zombie
0
0
0
zordoz
88
67
0
Figure 3: TWC Chaperone Details
6 Reproducibility
When rebuilding this document, subscribe to the gtp-benchmarks logger for information about the build:
PLTSTDERR="error info@gtp-benchmarks" raco setup gtp-benchmarks
6.1 Module Dependence Graphs
procedure
src* : (listof path-string?)
procedure
(complete-path->imported-modules p) → (listof complete-path?)
p : path-string?
Added in version 5.1 of package gtp-benchmarks.
procedure
p : path-string?
Added in version 5.1 of package gtp-benchmarks.
6.2 Type Information
procedure
src : path-string?
6.3 Counting Chaperones
procedure
(count-chaperones bin src) → chaperones-count/c
bin : racket-bin/count-chaperones? src : path-string?
procedure
x : any/c
Bibliography
| [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 |