11 Search Results for "Jones, Timothy"

Document
DOI: 10.4230/LIPIcs.ESA.2024.101
Time-Efficient Quantum Entropy Estimator via Samplizer

Authors: Qisheng Wang and Zhicheng Zhang

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ) and Rényi entropy S_α(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. - A quantum estimator for S(ρ) with time complexity Õ(N²), improving the prior best time complexity Õ(N⁶) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). - A quantum estimator for S_α(ρ) with time complexity Õ(N^{4/α-2}) for 0 < α < 1 and Õ(N^{4-2/α}) for α > 1, improving the prior best time complexity Õ(N^{6/α}) for 0 < α < 1 and Õ(N⁶) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε, N^{1/α-1}/ε^{1/α}}) for estimating S_α(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle U block-encodes a mixed quantum state ρ, any quantum query algorithm using Q queries to U can be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ~(Q²/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
Cite as

Qisheng Wang and Zhicheng Zhang. Time-Efficient Quantum Entropy Estimator via Samplizer. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 101:1-101:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2024.101,
  author =	{Wang, Qisheng and Zhang, Zhicheng},
  title =	{{Time-Efficient Quantum Entropy Estimator via Samplizer}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{101:1--101:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.101},
  URN =		{urn:nbn:de:0030-drops-211722},
  doi =		{10.4230/LIPIcs.ESA.2024.101},
  annote =	{Keywords: Quantum computing, entropy estimation, von Neumann entropy, R\'{e}nyi entropy, sample complexity}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.20
Constraint Modelling with LLMs Using In-Context Learning

Authors: Kostis Michailidis, Dimos Tsouros, and Tias Guns

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Constraint Programming (CP) allows for the modelling and solving of a wide range of combinatorial problems. However, modelling such problems using constraints over decision variables still requires significant expertise, both in conceptual thinking and syntactic use of modelling languages. In this work, we explore the potential of using pre-trained Large Language Models (LLMs) as coding assistants, to transform textual problem descriptions into concrete and executable CP specifications. We present different transformation pipelines with explicit intermediate representations, and we investigate the potential benefit of various retrieval-augmented example selection strategies for in-context learning. We evaluate our approach on 2 datasets from the literature, namely NL4Opt (optimisation) and Logic Grid Puzzles (satisfaction), and a heterogeneous set of exercises from a CP course. The results show that pre-trained LLMs have promising potential for initialising the modelling process, with retrieval-augmented in-context learning significantly enhancing their modelling capabilities.
Cite as

Kostis Michailidis, Dimos Tsouros, and Tias Guns. Constraint Modelling with LLMs Using In-Context Learning. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 20:1-20:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{michailidis_et_al:LIPIcs.CP.2024.20,
  author =	{Michailidis, Kostis and Tsouros, Dimos and Guns, Tias},
  title =	{{Constraint Modelling with LLMs Using In-Context Learning}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{20:1--20:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.20},
  URN =		{urn:nbn:de:0030-drops-207053},
  doi =		{10.4230/LIPIcs.CP.2024.20},
  annote =	{Keywords: Constraint Modelling, Constraint Acquisition, Constraint Programming, Large Language Models, In-Context Learning, Natural Language Processing, Named Entity Recognition, Retrieval-Augmented Generation, Optimisation}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.22
Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads

Authors: Xiaofei Carl Zang, Xiang Li, Kyle Metcalfe, Tuval Ben-Yehezkel, Ryan Kelley, and Mingfu Shao

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Modern sequencing technologies allow for the addition of short-sequence tags, known as anchors, to both ends of a captured molecule. Anchors are useful in assembling the full-length sequence of a captured molecule as they can be used to accurately determine the endpoints. One representative of such anchor-enabled technology is LoopSeq Solo, a synthetic long read (SLR) sequencing protocol. LoopSeq Solo also achieves ultra-high sequencing depth and high purity of short reads covering the entire captured molecule. Despite the availability of many assembly methods, constructing full-length sequence from these anchor-enabled, ultra-high coverage sequencing data remains challenging due to the complexity of the underlying assembly graphs and the lack of specific algorithms leveraging anchors. We present Anchorage, a novel assembler that performs anchor-guided assembly for ultra-high-depth sequencing data. Anchorage starts with a kmer-based approach for precise estimation of molecule lengths. It then formulates the assembly problem as finding an optimal path that connects the two nodes determined by anchors in the underlying compact de Bruijn graph. The optimality is defined as maximizing the weight of the smallest node while matching the estimated sequence length. Anchorage uses a modified dynamic programming algorithm to efficiently find the optimal path. Through both simulations and real data, we show that Anchorage outperforms existing assembly methods, particularly in the presence of sequencing artifacts. Anchorage fills the gap in assembling anchor-enabled data. We anticipate its broad use as anchor-enabled sequencing technologies become prevalent. Anchorage is freely available at https://github.com/Shao-Group/anchorage; the scripts and documents that can reproduce all experiments in this manuscript are available at https://github.com/Shao-Group/anchorage-test.
Cite as

Xiaofei Carl Zang, Xiang Li, Kyle Metcalfe, Tuval Ben-Yehezkel, Ryan Kelley, and Mingfu Shao. Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zang_et_al:LIPIcs.WABI.2024.22,
  author =	{Zang, Xiaofei Carl and Li, Xiang and Metcalfe, Kyle and Ben-Yehezkel, Tuval and Kelley, Ryan and Shao, Mingfu},
  title =	{{Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.22},
  URN =		{urn:nbn:de:0030-drops-206660},
  doi =		{10.4230/LIPIcs.WABI.2024.22},
  annote =	{Keywords: Genome assembly, de Bruijn graph, synthetic long reads, anchor-guided assembly, LoopSeq}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.50
Fast Algorithms for Geometric Consensuses

Authors: Sariel Har-Peled and Mitchell Jones

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.
Cite as

Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2020.50,
  author =	{Har-Peled, Sariel and Jones, Mitchell},
  title =	{{Fast Algorithms for Geometric Consensuses}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.50},
  URN =		{urn:nbn:de:0030-drops-122088},
  doi =		{10.4230/LIPIcs.SoCG.2020.50},
  annote =	{Keywords: Geometric optimization, centerpoint, voting games}
}
Document
DOI: 10.4230/LIPIcs.TIME.2019.20
On Verifying Timed Hyperproperties

Authors: Hsi-Ming Ho, Ruoyu Zhou, and Timothy M. Jones

Published in: LIPIcs, Volume 147, 26th International Symposium on Temporal Representation and Reasoning (TIME 2019)

Abstract
We study the satisfiability and model-checking problems for timed hyperproperties specified with HyperMTL, a timed extension of HyperLTL. Depending on whether interleaving of events in different traces is allowed, two possible semantics can be defined for timed hyperproperties: synchronous and asynchronous. While the satisfiability problem can be decided similarly as for HyperLTL regardless of the choice of semantics, we show that the model-checking problem for HyperMTL, unless the specification is alternation-free, is undecidable even when very restricted timing constraints are allowed. On the positive side, we show that model checking HyperMTL with quantifier alternations is possible under certain conditions in the synchronous semantics, or when there is a fixed bound on the length of the time domain.
Cite as

Hsi-Ming Ho, Ruoyu Zhou, and Timothy M. Jones. On Verifying Timed Hyperproperties. In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ho_et_al:LIPIcs.TIME.2019.20,
  author =	{Ho, Hsi-Ming and Zhou, Ruoyu and Jones, Timothy M.},
  title =	{{On Verifying Timed Hyperproperties}},
  booktitle =	{26th International Symposium on Temporal Representation and Reasoning (TIME 2019)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-127-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{147},
  editor =	{Gamper, Johann and Pinchinat, Sophie and Sciavicco, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2019.20},
  URN =		{urn:nbn:de:0030-drops-113782},
  doi =		{10.4230/LIPIcs.TIME.2019.20},
  annote =	{Keywords: Timed Automata, Temporal Logics, Cybersecurity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.24
Dynamic Geometric Data Structures via Shallow Cuttings

Authors: Timothy M. Chan

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We present new results on a number of fundamental problems about dynamic geometric data structures: 1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n^{11/12} for (i) and (ii), n^{7/8} for (iii) and (iv), and n^{2/3} for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings [Chan, SODA 2002]. 2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log^2n), and the amortized update time is O(log^4n) instead of O(log^5n) [Chan, SODA 2006; Kaplan et al., SODA 2017]. 3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log^4n) instead of O(log^7n) [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017].
Cite as

Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chan:LIPIcs.SoCG.2019.24,
  author =	{Chan, Timothy M.},
  title =	{{Dynamic Geometric Data Structures via Shallow Cuttings}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.24},
  URN =		{urn:nbn:de:0030-drops-104288},
  doi =		{10.4230/LIPIcs.SoCG.2019.24},
  annote =	{Keywords: dynamic data structures, convex hulls, nearest neighbor search, closest pair, shallow cuttings}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.21
On Locality-Sensitive Orderings and Their Applications

Authors: Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
For any constant d and parameter epsilon > 0, we show the existence of (roughly) 1/epsilon^d orderings on the unit cube [0,1)^d, such that any two points p, q in [0,1)^d that are close together under the Euclidean metric are "close together" in one of these linear orderings in the following sense: the only points that could lie between p and q in the ordering are points with Euclidean distance at most epsilon | p - q | from p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.
Cite as

Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones. On Locality-Sensitive Orderings and Their Applications. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ITCS.2019.21,
  author =	{Chan, Timothy M. and Har-Peled, Sariel and Jones, Mitchell},
  title =	{{On Locality-Sensitive Orderings and Their Applications}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.21},
  URN =		{urn:nbn:de:0030-drops-101140},
  doi =		{10.4230/LIPIcs.ITCS.2019.21},
  annote =	{Keywords: Approximation algorithms, Data structures, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.13
Object Inheritance Without Classes

Authors: Timothy Jones, Michael Homer, James Noble, and Kim Bruce

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
Which comes first: the object or the class? Language designers enjoy the conceptual simplicity of object-based languages (such as Emerald or Self) while many programmers prefer the pragmatic utility of classical inheritance (as in Simula and Java). Programmers in object-based languages have a tendency to build libraries to support traditional inheritance, and language implementations are often contorted to the same end. In this paper, we revisit the relationship between classes and objects. We model various kinds of inheritance in the context of an object-oriented language whose objects are not defined by classes, and explain why class inheritance and initialisation cannot be easily modelled purely by delegation.
Cite as

Timothy Jones, Michael Homer, James Noble, and Kim Bruce. Object Inheritance Without Classes. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 13:1-13:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ECOOP.2016.13,
  author =	{Jones, Timothy and Homer, Michael and Noble, James and Bruce, Kim},
  title =	{{Object Inheritance Without Classes}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{13:1--13:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.13},
  URN =		{urn:nbn:de:0030-drops-61077},
  doi =		{10.4230/LIPIcs.ECOOP.2016.13},
  annote =	{Keywords: Inheritance, Objects, Classes, Operational semantics}
}
Document
DOI: 10.4230/DARTS.2.1.6
Object Inheritance Without Classes (Artifact)

Authors: Timothy Jones and Michael Homer

Published in: DARTS, Volume 2, Issue 1, Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
This artifact is a PLT Redex implementation of the operational semantics presented in Object Inheritance Without Classes. It defines the core syntax and runtime semantics of the Graceless language, and then extends it in multiple different ways to produce the various implementations of object inheritance, including single and multiple inheritance. The implementation makes the semantics runnable, and precisely defines some behaviour which is defined informally in the paper.
Cite as

Timothy Jones and Michael Homer. Object Inheritance Without Classes (Artifact). In Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016). Dagstuhl Artifacts Series (DARTS), Volume 2, Issue 1, pp. 6:1-6:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{jones_et_al:DARTS.2.1.6,
  author =	{Jones, Timothy and Homer, Michael},
  title =	{{Object Inheritance Without Classes (Artifact)}},
  pages =	{6:1--6:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2016},
  volume =	{2},
  number =	{1},
  editor =	{Jones, Timothy and Homer, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.2.1.6},
  URN =		{urn:nbn:de:0030-drops-61278},
  doi =		{10.4230/DARTS.2.1.6},
  annote =	{Keywords: Inheritance, Objects, Classes, Operational semantics, PLT Redex}
}
Document
DOI: 10.4230/DARTS.1.1.4
Brand Objects for Nominal Typing (Artifact)

Authors: Timothy Jones, Michael Homer, and James Noble

Published in: DARTS, Volume 1, Issue 1, Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
In Brand Objects for Nominal Typing, we describe an implementation of a branding system for both runtime and static types. This artifact provides the extended form of Hopper, an interpreter for the Grace programming language, and extra modules which define both the dynamic objects and the modular static type checker. The extra modules extend the existing structural type checker in the provided version of Hopper, and are capable of statically checking code which interacts with statically determinable declarations of brand objects, including singleton brand constructors, brand sums, and dynamic variables which are known to contain some brand value at runtime. The dynamic brand objects extend this behaviour to the runtime, enforcing non-static contracts and allowing runtime type testing.
Cite as

Timothy Jones, Michael Homer, and James Noble. Brand Objects for Nominal Typing (Artifact). In Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015). Dagstuhl Artifacts Series (DARTS), Volume 1, Issue 1, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{jones_et_al:DARTS.1.1.4,
  author =	{Jones, Timothy and Homer, Michael and Noble, James},
  title =	{{Brand Objects for Nominal Typing (Artifact)}},
  pages =	{4:1--4:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2015},
  volume =	{1},
  number =	{1},
  editor =	{Jones, Timothy and Homer, Michael and Noble, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.1.1.4},
  URN =		{urn:nbn:de:0030-drops-55134},
  doi =		{10.4230/DARTS.1.1.4},
  annote =	{Keywords: brands, types, structural, nominal, Grace}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2015.198
Brand Objects for Nominal Typing

Authors: Timothy Jones, Michael Homer, and James Noble

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
Combinations of structural and nominal object typing in systems such as Scala, Whiteoak, and Unity have focused on extending existing nominal, class-based systems with structural subtyping. The typical rules of nominal typing do not lend themselves to such an extension, resulting in major modifications. Adding object branding to an existing structural system integrates nominal and structural typing without excessively complicating the type system. We have implemented brand objects to explicitly type objects, using existing features of the structurally typed language Grace, along with a static type checker which treats the brands as nominal types. We demonstrate that the brands are useful in an existing implementation of Grace, and provide a formal model of the extension to the language.
Cite as

Timothy Jones, Michael Homer, and James Noble. Brand Objects for Nominal Typing. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 198-221, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ECOOP.2015.198,
  author =	{Jones, Timothy and Homer, Michael and Noble, James},
  title =	{{Brand Objects for Nominal Typing}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{198--221},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.198},
  URN =		{urn:nbn:de:0030-drops-52314},
  doi =		{10.4230/LIPIcs.ECOOP.2015.198},
  annote =	{Keywords: brands, types, structural, nominal, Grace}
}
  • Refine by Author
  • 4 Homer, Michael
  • 4 Jones, Timothy
  • 3 Noble, James
  • 2 Chan, Timothy M.
  • 2 Har-Peled, Sariel
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 1 Applied computing → Molecular sequence analysis
  • 1 Computing methodologies → Discrete space search
  • 1 Computing methodologies → Natural language generation
  • 1 Mathematics of computing → Information theory
  • Show More...

  • Refine by Keyword
  • 2 Classes
  • 2 Grace
  • 2 Inheritance
  • 2 Objects
  • 2 Operational semantics
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 3 2019
  • 3 2024
  • 2 2015
  • 2 2016
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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