{"id":964929,"date":"2023-09-12T09:55:00","date_gmt":"2023-09-12T16:55:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=964929"},"modified":"2023-09-12T09:58:07","modified_gmt":"2023-09-12T16:58:07","slug":"fp2-fully-in-place-functional-programming-provides-memory-reuse-for-pure-functional-programs","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/fp2-fully-in-place-functional-programming-provides-memory-reuse-for-pure-functional-programs\/","title":{"rendered":"FP2: Fully In-Place Functional Programming provides memory reuse for pure functional programs\u00a0"},"content":{"rendered":"\n

This research paper was presented at the <\/em>28th<\/sup> ACM SIGPLAN International Conference on Functional Programming<\/em> (opens in new tab)<\/span><\/a> (ICFP), a premier forum for discussing design, implementations, principles, and uses of functional programming.<\/em><\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n

Functional programming languages offer a host of advantages, such as ensuring memory safety (opens in new tab)<\/span><\/a> and eliminating arbitrary side effects. This enables systematic analysis and compositional program construction, facilitating development of scalable and complex software systems. However, a drawback of functional programming is its tendency to liberally allocate new memory. We believe this characteristic has impeded widespread adoption in performance-critical domains. How can we overcome this limitation and harness the benefits of functional programming while maintaining efficient memory usage? <\/p>\n\n\n\n

To illustrate the issue, let\u2019s examine the well-known functional program to reverse a list in linear time using an accumulating parameter:<\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n

The reversal function is written in Koka (opens in new tab)<\/span><\/a>, a functional language developed at Microsoft that implements the techniques described in this blog post. Here, a list is either empty (as Nil<\/font><\/code>) or non-empty as a Cons<\/font>(head,tail)<\/code> node, and contains the first element as the head and the rest of the list as the tail<\/code>. <\/p>\n\n\n\n

In most functional languages, reversing a list this way allocates a fresh result list in the heap, where a list of integers from 1 to 10 is reversed, as shown in Figure 1.<\/p>\n\n\n\n

\"FP2:
Figure 1: The list [1..5] has already been reversed into acc, but we still must reverse the list [6..10]. <\/figcaption><\/figure>\n\n\n\n

As the list xs<\/code> is non-empty, we add its first element to our accumulating acc<\/code> parameter before recursing on the rest of the list xx<\/code>. As shown in Figure 2, this step allocates a new Cons<\/font><\/code> cell but also leaves the Cons<\/font><\/code> cell of xs<\/code> to be garbage collected. This is rather wasteful.<\/p>\n\n\n\n

\"FP2:
Figure 2: The lists after one step of recursion. The top Cons<\/font><\/code> cell on the left has become garbage, while the top Cons<\/font><\/code> cell on the right is freshly allocated.<\/figcaption><\/figure>\n\n\n\n

Fully in-place functional programming avoids allocation <\/h2>\n\n\n\n

Recent developments have made it possible to avoid such allocations. In particular, by using a compiler-guided reference counting algorithm called Perceus<\/a>, we can reuse objects in place whenever the objects are uniquely referenced at runtime. With such reuse, the reverse function can reverse a unique input list xs in-place <\/em>without allocating any fresh Cons<\/font><\/code> nodes, essentially switching the tail pointers of xs in-place. However, the dynamic nature of this form of reuse makes it hard to predict its application at runtime.\u00a0\u00a0<\/p>\n\n\n\n

In our paper, \u201cFP2<\/sup>: Fully in-Place Functional Programming<\/a>,\u201d which we\u2019re presenting at ICFP 2023 (opens in new tab)<\/span><\/a>, we describe the new fip<\/font><\/code> keyword. It statically checks that programs like the accumulating reverse function can execute in-place<\/em>, that is, using constant stack space without needing any heap allocation as long as the arguments are unique.<\/p>\n\n\n\n

<\/div>\n\n\n\n\t
\n\t\t\n\n\t\t

\n\t\tPODCAST SERIES<\/span>\n\t<\/p>\n\t\n\t

\n\t\t\t\t\t\t
\n\t\t\t\t\n\t\t\t\t\t\"Illustrated\n\t\t\t\t<\/a>\n\t\t\t<\/div>\n\t\t\t\n\t\t\t
\n\n\t\t\t\t\t\t\t\t\t

AI Testing and Evaluation: Learnings from Science and Industry<\/h2>\n\t\t\t\t\n\t\t\t\t\t\t\t\t

Discover how Microsoft is learning from other domains to advance evaluation and testing as a pillar of AI governance.<\/p>\n\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t
\n\t\t\t\t\t\t\n\t\t\t\t\t\t\tListen now\t\t\t\t\t\t<\/a>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t<\/div>\n\t<\/div>\n\t\n\n\n

Tree traversals and zippers<\/h2>\n\n\n\n

In fact, many familiar functions and algorithms satisfy our fully in-place criteria. For example, consider a binary tree with all the values at the leaves:<\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n

Now, suppose that we want to navigate through this tree, moving up and down in search of a particular element. You might add parent pointers, but in a functional language, there is an alternative solution originally proposed by G\u00e9rard Huet known as the zipper (opens in new tab)<\/span><\/a><\/em>:<\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n
\n\t
\n\t\t
\n\t\t\t\t\t\tTool<\/span>\n\t\t\tKoka<\/span> <\/span><\/a>\t\t\t\t\t<\/div>\n\t<\/article>\n<\/div>\n\n\n\n

The zipper stores subtrees along the path from the current node up to the root node. We can define operations on pairs consisting of this type of zipper and the current tree, enabling seamless movement through the tree. For example, the following function uses the zipper to move the focus to the left subtree:<\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n

Here, we move to the left subtree of the current node (if it exists) and extend the zipper data type accordingly. In his 1997, Huet already observed that such zipper operations could be implemented in place:<\/p>\n\n\n\n

Efficient destructive algorithms on binary trees may be programmed with these completely applicative primitives, which all use constant time, since they all reduce to local pointer manipulation<\/em>.<\/p><\/blockquote><\/figure>\n\n\n\n

In Koka, we can now make Huet\u2019s intuition precise, where the fip<\/font><\/code> keyword guarantees that left<\/code> is in place.\u00a0On closer examination, this might be surprising. While the list reversal example reused a Cons<\/font><\/code> node, here it seems like we may need to garbage collect a Bin<\/font><\/code> constructor and allocate a new BinL<\/font><\/code> constructor. Nonetheless, because both constructors have two fields, the previous Bin<\/font><\/code> memory location can still be reused (only updating the constructor tag). Our paper<\/a> provides the analysis details that enable this, rooted in the concept of “reuse credits.”<\/p>\n\n\n\n

Now, suppose we want to update all the values stored in a tree. Using a zipper, we can do this fully in place. While traversing, the zipper stores input tree fragments in order, using BinL<\/font><\/code> for unvisited and BinR<\/font><\/code> for visited subtrees. Reusing the zipper nodes allows in-order tree mapping without heap or stack usage. The tree map function starts by descending to the leftmost leaf, accumulating unvisited subtrees in BinL<\/font><\/code>. Once we hit the leftmost leaf, we apply the argument function f and work our way back up, recursively processing any unvisited subtrees, as shown in Figure 3.<\/p>\n\n\n\n

\"FP2:<\/figure>\n\n\n\n

The mutually tail-recursive app and down functions are fully in place. Each matched Bin<\/font><\/code> pairs with BinL<\/font><\/code>, and each BinL<\/font><\/code> with BinR<\/font><\/code>, ultimately leading to BinR<\/font><\/code> pairing with Bin<\/font><\/code>. The definition of tmap<\/code> may seem somewhat complex, but it is much simpler than its iterative imperative counterpart that uses direct pointer reversal.<\/p>\n\n\n\n

\"FP2:
Figure 3: The program after visiting the leaf containing f(2) on the given tree. The pointers in the zipper are reversed.<\/figcaption><\/figure>\n\n\n\n

Perspectives and further reading<\/h2>\n\n\n\n

Koka\u2019s new fip<\/font><\/code> keyword ensures that certain functions do not allocate and only use constant stack space, offering efficient and secure code execution akin to static linear types or Rust\u2019s borrow checker. This introduces a new paradigm for writing programs that are purely functional but can still execute in place. We consider this new technique to be a significant milestone on the path toward using high-level functional programming to develop robust software that delivers both competitive and predictable performance. <\/p>\n\n\n\n

To learn about fully in-place functional programming and the Koka language, start at the Koka homepage (opens in new tab)<\/span><\/a>. Koka implements a variety of innovative language features, including algebraic effect handlers and first-class constructor contexts. We encourage readers to continue exploring and experimenting with fully in-place programming. For example, try implementing skew binary heaps (opens in new tab)<\/span><\/a> in Koka. Can you demonstrate fully in-place heap union?<\/p>\n","protected":false},"excerpt":{"rendered":"

This research paper was presented at the 28th ACM SIGPLAN International Conference on Functional Programming (opens in new tab) (ICFP), a premier forum for discussing design, implementations, principles, and uses of functional programming. Functional programming languages offer a host of advantages, such as ensuring memory safety (opens in new tab) and eliminating arbitrary side effects. […]<\/p>\n","protected":false},"author":42735,"featured_media":964953,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_hide_image_in_river":0,"footnotes":""},"categories":[1],"tags":[],"research-area":[13560],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[264846],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-964929","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research-blog","msr-research-area-programming-languages-software-engineering","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":["Computing foundations"],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-events":[958992],"related-researchers":[{"type":"guest","value":"anton-lorenzen","user_id":"965007","display_name":"Anton Lorenzen","author_link":"Anton Lorenzen","is_active":true,"last_first":"Lorenzen, Anton","people_section":0,"alias":"anton-lorenzen"},{"type":"user_nicename","value":"Daan Leijen","user_id":31497,"display_name":"Daan Leijen","author_link":"Daan Leijen<\/a>","is_active":false,"last_first":"Leijen, Daan","people_section":0,"alias":"daan"},{"type":"guest","value":"wouter-swierstra","user_id":"965010","display_name":"Wouter Swierstra","author_link":"Wouter Swierstra","is_active":true,"last_first":"Swierstra, Wouter","people_section":0,"alias":"wouter-swierstra"}],"msr_type":"Post","featured_image_thumbnail":"\"FP2:","byline":"Anton Lorenzen, Daan Leijen<\/a>, and Wouter Swierstra","formattedDate":"September 12, 2023","formattedExcerpt":"This research paper was presented at the 28th ACM SIGPLAN International Conference on Functional Programming (opens in new tab) (ICFP), a premier forum for discussing design, implementations, principles, and uses of functional programming. Functional programming languages offer a host of advantages, such as ensuring memory…","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/964929","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/42735"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=964929"}],"version-history":[{"count":70,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/964929\/revisions"}],"predecessor-version":[{"id":967500,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/964929\/revisions\/967500"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/964953"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=964929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=964929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=964929"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=964929"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=964929"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=964929"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=964929"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=964929"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=964929"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=964929"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=964929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}