7 Search Results for "Lawall, Julia"

Document
DOI: 10.4230/LIPIcs.ITP.2025.7
A Verified Cost Model for Call-By-Push-Value

Authors: Zhuo Zoey Chen, Johannes Åman Pohjola, and Christine Rizkallah

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
The call-by-push-value λ-calculus allows for syntactically specifying the order of evaluation as part of the term language. Hence, it serves as a unifying language for embedding various evaluation strategies including call-by-value and call-by-name. Given the impact of call-by-push-value, it is remarkable that its adequacy as a model for computational complexity theory has not yet been studied. In this paper, we show that the call-by-push-value λ-calculus is reasonable for both time and space complexity. A reasonable cost model can encode other reasonable cost models with polynomial overhead in time and constant factor overhead in space. We achieve this by encoding call-by-push-value λ-calculus into Turing machines, following a simulation strategy by Forster et al.; for the converse direction, we prove that Levy’s encoding of the call-by-value λ-calculus has reasonable complexity bounds. The main results have been formalised in the HOL4 theorem prover.
Cite as

Zhuo Zoey Chen, Johannes Åman Pohjola, and Christine Rizkallah. A Verified Cost Model for Call-By-Push-Value. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITP.2025.7,
  author =	{Chen, Zhuo Zoey and \r{A}man Pohjola, Johannes and Rizkallah, Christine},
  title =	{{A Verified Cost Model for Call-By-Push-Value}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.7},
  URN =		{urn:nbn:de:0030-drops-246067},
  doi =		{10.4230/LIPIcs.ITP.2025.7},
  annote =	{Keywords: lambda calculus, formalizations of computational models, computability theory, HOL, call-by-push-value reduction, time and space complexity, abstract machines}
}
Document
DOI: 10.4230/OASIcs.Programming.2025.23
The Pyttern Program Query Language

Authors: Julien Liénard, Kim Mens, and Siegfried Nijssen

Published in: OASIcs, Volume 134, Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)

Abstract
Despite the availability of numerous tools and languages for detecting structural patterns in programs, their complexity often presents a steep learning curve. This highlights the need for a program query language that is easier to learn, use, and read while remaining sufficiently expressive for defining and detecting relevant structural coding patterns in program code. To address this challenge, we present Pyttern, a query language that extends Python syntax with regular-expression-inspired wildcards, enabling intuitive pattern-based querying of Python code. Its implementation relies upon a custom pushdown automaton describing how to match patterns over program parse trees, thus providing a robust foundation for structural code analysis. We evaluate Pyttern’s usability and effectiveness through a study involving 35 master’s students, who were asked to write seven different patterns to identify known programming misconceptions. The results demonstrate that Pyttern is both easy to learn and practical to use, at least for analysing small-scale programs.
Cite as

Julien Liénard, Kim Mens, and Siegfried Nijssen. The Pyttern Program Query Language. In Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025). Open Access Series in Informatics (OASIcs), Volume 134, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lienard_et_al:OASIcs.Programming.2025.23,
  author =	{Li\'{e}nard, Julien and Mens, Kim and Nijssen, Siegfried},
  title =	{{The Pyttern Program Query Language}},
  booktitle =	{Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)},
  pages =	{23:1--23:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-382-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{134},
  editor =	{Edwards, Jonathan and Perera, Roly and Petricek, Tomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Programming.2025.23},
  URN =		{urn:nbn:de:0030-drops-243075},
  doi =		{10.4230/OASIcs.Programming.2025.23},
  annote =	{Keywords: Pyttern, Program Query Languages, Python, Pattern Matching, Parse Tree, Pushdown Automaton, Static Code Analysis, Wildcards, Tree Pattern Matching}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.18
On the Origins of Coccinelle

Authors: Julia Lawall

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

Abstract
Coccinelle is a program-transformation system for C code. It has been under development since 2005 and has been extensively used on the Linux kernel. The design of Coccinelle was inspired in part by the author’s previous experience in using Stratego/XT, developed by Eelco Visser. This paper reflects on some of Coccinelle’s design choices and their relation to Eelco Visser’s work.
Cite as

Julia Lawall. On the Origins of Coccinelle. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 18:1-18:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lawall:OASIcs.EVCS.2023.18,
  author =	{Lawall, Julia},
  title =	{{On the Origins of Coccinelle}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{18:1--18:11},
  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.18},
  URN =		{urn:nbn:de:0030-drops-177884},
  doi =		{10.4230/OASIcs.EVCS.2023.18},
  annote =	{Keywords: Linux kernel, Coccinelle, Stratego/XT, program transformation}
}
Document
Artifact
DOI: 10.4230/DARTS.5.2.10
Semantic Patches for Java Program Transformation (Artifact)

Authors: Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo

Published in: DARTS, Volume 5, Issue 2, Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
The program transformation tool Coccinelle is designed for making changes that is required in many locations within a software project. It has been shown to be useful for C code and has been been adopted for use in the Linux kernel by many developers. Over 6000 commits mentioning the use of Coccinelle have been made in the Linux kernel. Our artifact, Coccinelle4J, is an extension to Coccinelle in order for it to apply program transformations to Java source code. This artifact accompanies our experience report "Semantic Patches for Java Program Transformation", in which we show a case study of applying code transformations to upgrade usage of deprecated Android API methods to replacement API methods.
Cite as

Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo. Semantic Patches for Java Program Transformation (Artifact). In Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 2, pp. 10:1-10:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{kang_et_al:DARTS.5.2.10,
  author =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  title =	{{Semantic Patches for Java Program Transformation}},
  pages =	{10:1--10:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{2},
  editor =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.2.10},
  URN =		{urn:nbn:de:0030-drops-107875},
  doi =		{10.4230/DARTS.5.2.10},
  annote =	{Keywords: Java, semantic patches, automatic program transformation}
}
Document
Experience Report
DOI: 10.4230/LIPIcs.ECOOP.2019.22
Semantic Patches for Java Program Transformation (Experience Report)

Authors: Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
Developing software often requires code changes that are widespread and applied to multiple locations. There are tools for Java that allow developers to specify patterns for program matching and source-to-source transformation. However, to our knowledge, none allows for transforming code based on its control-flow context. We prototype Coccinelle4J, an extension to Coccinelle, which is a program transformation tool designed for widespread changes in C code, in order to work on Java source code. We adapt Coccinelle to be able to apply scripts written in the Semantic Patch Language (SmPL), a language provided by Coccinelle, to Java source files. As a case study, we demonstrate the utility of Coccinelle4J with the task of API migration. We show 6 semantic patches to migrate from deprecated Android API methods on several open source Android projects. We describe how SmPL can be used to express several API migrations and justify several of our design decisions.
Cite as

Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo. Semantic Patches for Java Program Transformation (Experience Report). In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.ECOOP.2019.22,
  author =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  title =	{{Semantic Patches for Java Program Transformation}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{22:1--22:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.22},
  URN =		{urn:nbn:de:0030-drops-108140},
  doi =		{10.4230/LIPIcs.ECOOP.2019.22},
  annote =	{Keywords: Program transformation, Java}
}
Document
DOI: 10.4230/LITES-v001-i002-a001
Blocking Optimality in Distributed Real-Time Locking Protocols

Authors: Björn Bernhard Brandenburg

Published in: LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2

Abstract
Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shared-memory multiprocessor locking protocols (which require resources to be accessible from all processors) has established asymptotically tight bounds of Ω(m) and Ω(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively, where m denotes the total number of processors and n denotes the number of tasks. In this paper, it is shown that, in the case of distributed semaphore protocols, there exist two different task allocation scenarios that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronization processors (i.e., processors hosting critical sections), Ω(Φ · n) maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where Φ denotes the ratio of the maximum response time to the shortest period. In contrast, in the case of disjoint task allocation (i.e., if application tasks may not be assigned to synchronization processors), only Ω(m) and Ω(n) maximum pi-blocking is fundamentally unavoidable under suspension-oblivious and suspension-aware analysis, respectively, as in the shared-memory case. These bounds are shown to be asymptotically tight with the construction of two new distributed real-time locking protocols that ensure O(m) and O(n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively.
Cite as

Björn Bernhard Brandenburg. Blocking Optimality in Distributed Real-Time Locking Protocols. In LITES, Volume 1, Issue 2 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 2, pp. 01:1-01:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{brandenburg:LITES-v001-i002-a001,
  author =	{Brandenburg, Bj\"{o}rn Bernhard},
  title =	{{Blocking Optimality in Distributed Real-Time Locking Protocols}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:22},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i002-a001},
  URN =		{urn:nbn:de:0030-drops-192479},
  doi =		{10.4230/LITES-v001-i002-a001},
  annote =	{Keywords: Distributed multiprocessor real-time systems, Real-time locking, Priority inversion, Blocking optimality}
}
Document
DOI: 10.4230/DagSemProc.07041.12
Towards Class-Based Dynamic Voltage Scaling for Multimedia Applications

Authors: Richard Urunuela, Gilles Muller, and Julia Lawall

Published in: Dagstuhl Seminar Proceedings, Volume 7041, Power-aware Computing Systems (2007)

Abstract
Video display has significant, but highly variable, CPU requirements. As such, it is an attractive target for power management via dynamic voltage scaling. In previous work, we have proposed a dynamic voltage scaling algorithm directed to the context of video kiosks, in which a minimal frequency for each frame can be determined experimentally based on observations taken during the first few iterations of the video. In this paper, we review that work, and begin to consider how such an approach can be adapted to the more common case where a video is only played once, on hardware that is not known in advance.
Cite as

Richard Urunuela, Gilles Muller, and Julia Lawall. Towards Class-Based Dynamic Voltage Scaling for Multimedia Applications. In Power-aware Computing Systems. Dagstuhl Seminar Proceedings, Volume 7041, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{urunuela_et_al:DagSemProc.07041.12,
  author =	{Urunuela, Richard and Muller, Gilles and Lawall, Julia},
  title =	{{Towards Class-Based Dynamic Voltage Scaling for Multimedia Applications}},
  booktitle =	{Power-aware Computing Systems},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7041},
  editor =	{Luca Benini and Naehyuck Chang and Ulrich Kremer and Christian W. Probst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07041.12},
  URN =		{urn:nbn:de:0030-drops-11088},
  doi =		{10.4230/DagSemProc.07041.12},
  annote =	{Keywords: Dynamic voltage scaling, multimedia applications, embedded systems}
}
  • Refine by Type
  • 7 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023
  • 2 2019
  • 1 2014
  • 1 2007

  • Refine by Author
  • 4 Lawall, Julia
  • 3 Muller, Gilles
  • 2 Jiang, Lingxiao
  • 2 Kang, Hong Jin
  • 2 Lo, David
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 OASIcs
  • 1 DARTS
  • 1 LITES
  • 1 DagSemProc

  • Refine by Classification
  • 2 Software and its engineering → Software notations and tools
  • 1 Computer systems organization → Real-time systems
  • 1 Information systems → Query languages
  • 1 Software and its engineering → Automated static analysis
  • 1 Software and its engineering → Software evolution
  • Show More...

  • Refine by Keyword
  • 2 Java
  • 1 Blocking optimality
  • 1 Coccinelle
  • 1 Distributed multiprocessor real-time systems
  • 1 Dynamic voltage scaling
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact