Skip to content

Instantly share code, notes, and snippets.

@jdh30
Last active February 28, 2019 03:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jdh30/073d1af8bc84f38a700e7d711da3e628 to your computer and use it in GitHub Desktop.
Save jdh30/073d1af8bc84f38a700e7d711da3e628 to your computer and use it in GitHub Desktop.
A program for which prompt collection is practically impossible
(*
The resizable array xs is required for the first half of the execution of
this "test" function but not the last half. Collecting xs as early as possible
would mean collecting it halfway through the execution of "test" but this
is practically impossible. Doing so in general is equivalent to solving the
halting problem.
*)
let next n =
6364136223846793005UL*n + 1442695040888963407UL
let rec test (xs: ResizeArray<_>) n =
xs.Add n
let n = next n
if n = 7331588424831733315UL then
printfn "%d" xs.[n % uint64 xs.Count |> int]
if n <> 10556961279111748739UL then
test xs n
test (ResizeArray()) 3UL
@jduey
Copy link

jduey commented Feb 28, 2019

Quick and dirty results using "time -v"

Toccata:
Command being timed: "./promptness"
User time (seconds): 0.21
Maximum resident set size (kbytes): 34584

FSharp
Command being timed: "./promptness.exe"
User time (seconds): 0.03
Maximum resident set size (kbytes): 40608

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment