DROPS

Document

DOI: 10.4230/OASIcs.EVCS.2023.16

Typed Multi-Language Strategy Combinators

Authors: James Koppel

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract

Strategy combinators (also called strategic programming) are a technique for modular program transformation construction invented by Bas Luttik and Eelco Visser, best known for their instantiation in the Stratego language. Traditional implementations are dynamically typed, and struggle to represent transformations that can be usefully applied to some types, but not all. We present the design of our strategy-combinator library compstrat, a library for type-safe strategy combinators which run on Patrick Bahr’s compositional datatypes. We show how strategy combinators and compositional datatypes fuse elegantly, allowing the creation of type-preserving program transformations which operate only on datatypes satisfying certain properties. With this technique, it becomes possible to compactly define program transformations that operate on multiple programming languages. compstrat is part of the Cubix framework and has been used to build four program transformations, each of which operates on at least three languages.

Cite as

James Koppel. Typed Multi-Language Strategy Combinators. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{koppel:OASIcs.EVCS.2023.16,
  author =	{Koppel, James},
  title =	{{Typed Multi-Language Strategy Combinators}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{16:1--16:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.16},
  URN =		{urn:nbn:de:0030-drops-177865},
  doi =		{10.4230/OASIcs.EVCS.2023.16},
  annote =	{Keywords: program transformation, strategic programming}
}

Document

DOI: 10.4230/LIPIcs.FUN.2022.17

Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports

Authors: James Koppel and Yun William Yu

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

Some Olympic sports, like the marathon, are purely feats of human athleticism. But in others such as gymnastics, athletes channel their athleticism into a routine of skills. In these disciplines, designing the highest-scoring routine can be a challenging problem, because the routines are judged via a combination of artistic merit, which is largely subjective, and technical difficulty, which comes with complicated but objective scoring rules. Notably, since the 2006 Code of Points, FIG (International Gymnastics Federation) has sought to make gymnastics scoring more objective by encoding more of the score in those objective technical side of scoring, and in this paper, we show how that push is reflected in the computational complexity of routine optimization. Here, we analyze the purely-technical component of the scoring rules of routines in 17 different events across 5 Olympic sports. We identify four attributes that classify the common rules found in scoring functions, and, for each combination of attributes, prove hardness results or provide algorithms for designing the highest-scoring routine according to the objective technical component of the scoring functions. Ultimately, we discover that optimal routine construction for events in artistic, rhythmic, and trampoline gymnastics is NP-hard, while optimal routine construction for all other sports is in P.

Cite as

James Koppel and Yun William Yu. Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koppel_et_al:LIPIcs.FUN.2022.17,
  author =	{Koppel, James and Yu, Yun William},
  title =	{{Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.17},
  URN =		{urn:nbn:de:0030-drops-159877},
  doi =		{10.4230/LIPIcs.FUN.2022.17},
  annote =	{Keywords: complexity, games, sports}
}

Search Results

Documents authored by Koppel, James

Typed Multi-Language Strategy Combinators

Abstract

Cite as

Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports

Abstract

Cite as

Thanks for your feedback!

Could not send message