{"action":"closed","issue":{"url":"https://api.github.com/repos/GaloisInc/cryptol/issues/488","repository_url":"https://api.github.com/repos/GaloisInc/cryptol","labels_url":"https://api.github.com/repos/GaloisInc/cryptol/issues/488/labels{/name}","comments_url":"https://api.github.com/repos/GaloisInc/cryptol/issues/488/comments","events_url":"https://api.github.com/repos/GaloisInc/cryptol/issues/488/events","html_url":"https://github.com/GaloisInc/cryptol/issues/488","id":279102484,"number":488,"title":"Slow evaluation","user":{"login":"benjaminjellison","id":17770429,"avatar_url":"https://avatars1.githubusercontent.com/u/17770429?v=4","gravatar_id":"","url":"https://api.github.com/users/benjaminjellison","html_url":"https://github.com/benjaminjellison","followers_url":"https://api.github.com/users/benjaminjellison/followers","following_url":"https://api.github.com/users/benjaminjellison/following{/other_user}","gists_url":"https://api.github.com/users/benjaminjellison/gists{/gist_id}","starred_url":"https://api.github.com/users/benjaminjellison/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benjaminjellison/subscriptions","organizations_url":"https://api.github.com/users/benjaminjellison/orgs","repos_url":"https://api.github.com/users/benjaminjellison/repos","events_url":"https://api.github.com/users/benjaminjellison/events{/privacy}","received_events_url":"https://api.github.com/users/benjaminjellison/received_events","type":"User","site_admin":false},"labels":[{"id":859298553,"url":"https://api.github.com/repos/GaloisInc/cryptol/labels/exponential%20slowdown","name":"exponential slowdown","color":"000000","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2017-12-04T18:38:30Z","updated_at":"2018-03-22T00:55:24Z","closed_at":"2018-03-22T00:55:24Z","author_association":"NONE","body":"Using version 942173b and the code, this command takes a long time to evaluate:\r\n```\r\ntake`{80} (drop`{100} (threelfsr `0x012 `0x012 `0x012))\r\n```\r\nWhen running it 2.4 it evaluates in less than a second; in 2.5 it takes maybe around 20 minutes.\r\n\r\nHere is the code:\r\n```\r\nxorlist list = ls!0\r\n  where\r\n   ls = [False] # [ a ^ b | a <- ls | b <- list]\r\n\r\nlfsr_states : {a, n} (fin a, fin n, 1 <= a, 1 <= n)\r\n\t    => [a][width n]   //taps\r\n\t    -> [n]\t      //seed\r\n\t    -> [inf][n]\t      //stream of lfsr_states\r\n\r\nlfsr_states taps seed = states\r\n   where\r\n    next_state s = (tail s) # [xorlist (s@@taps)]\r\n    states = [seed] # [next_state s | s <- states]\r\n\r\n\r\nlfsr_bits : {a, n} (fin a, fin n, 1 <= a, 1 <= n)\r\n\t    => [a][width n]   //taps\r\n\t    -> [n]\t      //seed\r\n\t    -> [inf]\t      //stream of bits\r\n\r\nlfsr_bits taps seed = [ st @ 0 | st <- lfsr_states taps seed ]\r\n\r\nmaj a b c = (a /\\ b) \\/ (b /\\ c) \\/ (a /\\ c)\r\n\r\nthreelfsr : [10] -> [10] -> [10] -> [inf]\r\nthreelfsr f0 f1 f2 = bits\r\n   where\r\n    s0 = lfsr_bits [0,3] f0\r\n    s1 = lfsr_bits [0,2] f1\r\n    s2 = lfsr_bits [0,4] f2\r\n    bits = [ maj a b c | a <- s0 | b <- s1 | c <- s2 ]\r\n```"}}
{"actor":{"display_login":"brianhuffman"}}