{"action":"created","issue":{"url":"https://api.github.com/repos/plt/racket/issues/952","labels_url":"https://api.github.com/repos/plt/racket/issues/952/labels{/name}","comments_url":"https://api.github.com/repos/plt/racket/issues/952/comments","events_url":"https://api.github.com/repos/plt/racket/issues/952/events","html_url":"https://github.com/plt/racket/issues/952","id":84077515,"number":952,"title":"racket/match appears to evaluate ?-based predicates many times on the same inputs","user":{"login":"rfindler","id":399024,"avatar_url":"https://avatars.githubusercontent.com/u/399024?v=3","gravatar_id":"","url":"https://api.github.com/users/rfindler","html_url":"https://github.com/rfindler","followers_url":"https://api.github.com/users/rfindler/followers","following_url":"https://api.github.com/users/rfindler/following{/other_user}","gists_url":"https://api.github.com/users/rfindler/gists{/gist_id}","starred_url":"https://api.github.com/users/rfindler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rfindler/subscriptions","organizations_url":"https://api.github.com/users/rfindler/orgs","repos_url":"https://api.github.com/users/rfindler/repos","events_url":"https://api.github.com/users/rfindler/events{/privacy}","received_events_url":"https://api.github.com/users/rfindler/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-06-02T15:41:03Z","updated_at":"2015-06-02T16:31:04Z","closed_at":null,"body":"The printouts you get from running this code show that the `L4e?` predicate is being called many many times on the same inputs, presumably because the predicates in the `?` patterns can be called many times. This makes this function take exponential time.\r\n\r\nI'm not sure if this is avoidable, but I have a vague memory of this coming up before and I don't see anything in the documentation about it.\r\n\r\nThe code below prints out a stream of numbers -- those numbers are the number of times that the same argument is supplied to `L4e?` and they get quite large. (4,379,424 is the maximum, I believe.)\r\n\r\n```\r\n#lang racket/base\r\n(require racket/match\r\n         racket/list)\r\n\r\n(define ht (make-hash))\r\n(define (L4e? e-exp)\r\n  (hash-set! ht e-exp (+ (hash-ref ht e-exp 0) 1))\r\n  (printf \"~a\\n\" (hash-ref ht e-exp 0))\r\n  (match e-exp\r\n    [`(,(? is-biop?) ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(,_ ,(? L4e?)) #t]\r\n    [`(new-array ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(new-tuple ,(? L4e?) ...) #t]\r\n    [`(aref ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(aset ,(? L4e?) ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(alen ,(? L4e?)) #t]\r\n    [`(print ,(? L4e?)) #t]\r\n    [`(make-closure ,(? symbol?) ,(? L4e?)) #t]\r\n    [`(closure-proc ,(? L4e?)) #t]\r\n    [`(begin ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(closure-vars ,(? L4e?)) #t]\r\n    [`(let ((,(? symbol?) ,(? L4e?))) ,(? L4e?)) #t]\r\n    [`(if ,(? L4e?) ,(? L4e?) ,(? L4e?)) #t]\r\n    [`(,(? L4e?) ...) #t]\r\n    [(? L3v?) #t]\r\n    [_ #f]))\r\n\r\n(define (is-biop? sym) (or (is-aop? sym) (is-cmp? sym)))\r\n(define (is-aop? sym) (memq sym '(+ - *)))\r\n(define (is-cmp? sym) (memq sym '(< <= =)))\r\n(define (L3v? v) (or (number? v) (symbol? v)))\r\n\r\n(printf \"starting\\n\")\r\n(time      \r\n (L4e? '(let ((less_than (make-closure :lambda_0 (new-tuple))))\r\n          (let ((L5_swap (make-closure :lambda_1 (new-tuple))))\r\n            (let ((L5_sort_helper (new-tuple 0)))\r\n              (begin\r\n                (aset L5_sort_helper 0 (make-closure :lambda_2 (new-tuple L5_sort_helper L5_swap)))\r\n                (let ((L5_sort (new-tuple 0)))\r\n                  (begin\r\n                    (aset L5_sort 0 (make-closure :lambda_3 (new-tuple L5_sort_helper L5_sort)))\r\n                    (print (let ((f (aref L5_sort 0)))\r\n                             ((closure-proc f)\r\n                              (closure-vars f)\r\n                              (new-tuple 3 1 9 4 5 6 2 8 7 10)\r\n                              less_than)))))))))))\r\n```"},"comment":{"url":"https://api.github.com/repos/plt/racket/issues/comments/108007264","html_url":"https://github.com/plt/racket/issues/952#issuecomment-108007264","issue_url":"https://api.github.com/repos/plt/racket/issues/952","id":108007264,"user":{"login":"jeapostrophe","id":232698,"avatar_url":"https://avatars.githubusercontent.com/u/232698?v=3","gravatar_id":"","url":"https://api.github.com/users/jeapostrophe","html_url":"https://github.com/jeapostrophe","followers_url":"https://api.github.com/users/jeapostrophe/followers","following_url":"https://api.github.com/users/jeapostrophe/following{/other_user}","gists_url":"https://api.github.com/users/jeapostrophe/gists{/gist_id}","starred_url":"https://api.github.com/users/jeapostrophe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jeapostrophe/subscriptions","organizations_url":"https://api.github.com/users/jeapostrophe/orgs","repos_url":"https://api.github.com/users/jeapostrophe/repos","events_url":"https://api.github.com/users/jeapostrophe/events{/privacy}","received_events_url":"https://api.github.com/users/jeapostrophe/received_events","type":"User","site_admin":false},"created_at":"2015-06-02T16:31:04Z","updated_at":"2015-06-02T16:31:04Z","body":"The documentation of 'match' says this at the bottom: \"Note that the\nmatching process may destructure the input multiple times, and may\nevaluate expressions embedded in patterns such as (app expr pat) in\narbitrary order, or multiple times. Therefore, such expressions must\nbe safe to call multiple times, or in an order other than they appear\nin the original program.\"\n\nJay\n\nOn Tue, Jun 2, 2015 at 12:25 PM, Robby Findler <notifications@github.com> wrote:\n> On Tue, Jun 2, 2015 at 11:23 AM, Jay McCarthy <notifications@github.com>\n> wrote:\n>\n>> This happened to me once before. My ? fund had effects that were\n>> repeating.\n>> Sam said don't do it and that it has to do with the reordering and\n>> duplication in the match row algorithm.\n>>\n>\n> Yeah, that makes sense to me.\n>\n> So I\"ll wait for \"official confirmation\" and then suggest that we explain\n> this super clearly in the docs so hopefully others don't run into this\n> pitfall.\n>\n> Robby\n>\n> —\n> Reply to this email directly or view it on GitHub.\n\n\n\n-- \nJay McCarthy\nhttp://jeapostrophe.github.io\n\n           \"Wherefore, be not weary in well-doing,\n      for ye are laying the foundation of a great work.\nAnd out of small things proceedeth that which is great.\"\n                          - D&C 64:33\n"}}