DROPS

Document

Artifact

What If We Don't Pop the Stack? The Return of 2nd-Class Values (Artifact)

Authors: Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf

Published in: DARTS, Volume 8, Issue 2, Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract

The main paper presents λ^{1/2}_{↩}, a type system and operational semantics with 2nd-class values and delayed stack reclamation. This artifact contains a compiler implementation of the calculus in Scala Native, the code for the case studies shown in the paper, and code for reproducing the evaluation.

Cite as

Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf. What If We Don't Pop the Stack? The Return of 2nd-Class Values (Artifact). In Special Issue of the 36th European Conference on Object-Oriented Programming (ECOOP 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 2, pp. 26:1-26:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{xhebraj_et_al:DARTS.8.2.26,
  author =	{Xhebraj, Anxhelo and Bra\v{c}evac, Oliver and Wei, Guannan and Rompf, Tiark},
  title =	{{What If We Don't Pop the Stack? The Return of 2nd-Class Values (Artifact)}},
  pages =	{26:1--26:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{2},
  editor =	{Xhebraj, Anxhelo and Bra\v{c}evac, Oliver and Wei, Guannan and Rompf, Tiark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.2.26},
  URN =		{urn:nbn:de:0030-drops-162247},
  doi =		{10.4230/DARTS.8.2.26},
  annote =	{Keywords: Call stack, closures, stack allocation, memory management, 2nd-class values, capabilities, effects}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2022.15

What If We Don't Pop the Stack? The Return of 2nd-Class Values

Authors: Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)

Abstract

Using a stack for managing the local state of procedures as popularized by Algol is a simple but effective way to achieve a primitive form of automatic memory management. Hence, the call stack remains the backbone of most programming language runtimes to the present day. However, the appealing simplicity of the call stack model comes at the price of strictly enforced limitations: since every function return pops the stack, it is difficult to return stack-allocated data from a callee upwards to its caller - especially variable-size data such as closures. This paper proposes a solution by introducing a small tweak to the usual stack semantics. We design a type system that tracks the underlying storage mode of values, and when a function returns a stack-allocated value, we just don't pop the stack! Instead, the stack frame is de-allocated together with a parent the next time a heap-allocated value or primitive is returned. We identify a range of use cases where this delayed-popping strategy is beneficial, ranging from closures to trait objects to other types of variable-size data. Our evaluation shows that this execution model reduces heap and GC pressure and recovers spatial locality of programs improving execution time between 10% and 25% with respect to standard execution.

Cite as

Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf. What If We Don't Pop the Stack? The Return of 2nd-Class Values. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 15:1-15:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{xhebraj_et_al:LIPIcs.ECOOP.2022.15,
  author =	{Xhebraj, Anxhelo and Bra\v{c}evac, Oliver and Wei, Guannan and Rompf, Tiark},
  title =	{{What If We Don't Pop the Stack? The Return of 2nd-Class Values}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{15:1--15:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.15},
  URN =		{urn:nbn:de:0030-drops-162430},
  doi =		{10.4230/LIPIcs.ECOOP.2022.15},
  annote =	{Keywords: Call stack, closures, stack allocation, memory management, 2nd-class values, capabilities, effects}
}

Search Results

Documents authored by Xhebraj, Anxhelo

What If We Don't Pop the Stack? The Return of 2nd-Class Values (Artifact)

Abstract

Cite as

What If We Don't Pop the Stack? The Return of 2nd-Class Values

Abstract

Cite as

Thanks for your feedback!

Could not send message