{"id":1209,"date":"2012-12-10T23:41:55","date_gmt":"2012-12-10T22:41:55","guid":{"rendered":"http:\/\/cerezo.name\/blog\/?p=1209"},"modified":"2024-10-14T13:45:36","modified_gmt":"2024-10-14T11:45:36","slug":"on-the-never-ending-quest-of-functional-programming","status":"publish","type":"post","link":"http:\/\/cerezo.name\/blog\/2012\/12\/10\/on-the-never-ending-quest-of-functional-programming\/","title":{"rendered":"On The Never-Ending Quest of Functional Programming"},"content":{"rendered":"<p style=\"text-align: justify;\">Functional programming has been in the top of the hype-cycle for decades: no side effects, methods written in a purely mathematical style, strong type systems\u2026 What\u2019s not to like about functional programming? It\u2019s even a loaded term! Just ask someone: \u201cBut is not your code&nbsp;<em>functional <\/em>, yet?\u201d<\/p>\n<p style=\"text-align: justify;\">Although the Turing machine (imperative) model of computation was shown to be equivalent to the \u03bb\u2011calculus (functional), there\u2019s actually a long gap in its asymptotics.<\/p>\n<p style=\"text-align: justify;\">Start with the most simple of the data structures, the array: in a purely functional style of programming, to update an array you would need O(log <em>N<\/em>) time, but in an imperative language it\u2019s just O(1). And this is not a specific problem with arrays, it\u2019s the standard behaviour within pure functional programming languages due to the their overrated immutability of data: in \u201c<a href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.36.670\" target=\"_blank\" rel=\"noopener\">Pure versus Impure <span class=\"caps\">LISP<\/span><\/a>\u201d, it\u2019s shown that O(<em>N<\/em>) functional programs written with lazy, non-strict evaluation semantics can be translated to a purely functional style in O(<em>N<\/em>&nbsp;log <em>N<\/em>). That is, at worst an O(log <em>N<\/em>) slowdown per operation may occur by simulating mutable memory access: immutability carries a very high cost, indeed.<span id=\"vd2fe19f3c8\"><\/span><\/p>\n<p style=\"text-align: justify;\">In practice, extensions to the pure functional paradigm have been considered to address the need to directly reference and change the state of variables (monads in Haskell), and most algorithms can be implemented efficiently by using purely functional programming, but it also involves extensive and difficult knowledge (\u201c[amazon_link id=\u201c0521663504\u201d target=\u201c_blank\u201d ]Purely Functional Data Structures[\/amazon_link]\u201d) for even the most basic of data structures, and the recognition &nbsp;that they require a significant slowdown by constant factors and <span class=\"caps\">CPU<\/span> stalling due to many cache misses.<\/p>\n<p style=\"text-align: justify;\">And, as if that is not enough, debugging any functional program is a quest in itself: I would say that it\u2019s an order of magnitude more difficult than an imperative language, vastly increasing software maintenance costs.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Functional programming has been in the top of the hype-cycle for decades: no side effects, methods written in a purely mathematical style, strong type systems\u2026 What\u2019s not to like about functional programming? It\u2019s even a loaded term! Just ask someone: \u201cBut is not your code&nbsp;functional , yet?\u201d Although the Turing machine (imperative) model of computation&nbsp;[\u2026]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"wp_typography_post_enhancements_disabled":false,"ngg_post_thumbnail":0},"categories":[15],"tags":[],"_links":{"self":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1209"}],"collection":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/comments?post=1209"}],"version-history":[{"count":3,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1209\/revisions"}],"predecessor-version":[{"id":1565,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1209\/revisions\/1565"}],"wp:attachment":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/media?parent=1209"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/categories?post=1209"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/tags?post=1209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}