Jens Palsberg
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Jens Palsberg has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
Michael I. Schwartzbach
Department of Computer Science, University of Aarhus, Ny Munkegade, DK‐8000 Århus C, Denmark
14 shared publications- Michael I. Schwartzbach
Computer Science Department, Aarhus University, Ny Munkegade, DK-8000 Århus C, Denmark
3 shared publications - Karoline Malmkjær
Aarhus University
2 shared publications - Ole Agesen
Department of Computer Science, Stanford University, Stanford, CA 94305, U.S.A.
2 shared publications - Olivier Danvy
Computer Science Department Aarhus University
2 shared publications - Allan Cheng
Computer Science Department Aarhus University Ny Munkegade DK-8000 Aarhus C Denmark
1 shared publication
Latest Publications
- 1 January 1996
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 6 (2) , 269-298
Generating action compilers by partial evaluation
Compiler generation based on Mosses' action semantics has been studied by Brown, Moura, and Watt, and also by the second author. The core of each of their systems is a handwritten action compiler, producing either C or machine code. We have obtained an action compiler in a much simpler way: by partial evaluation of an action interpreter. Even though our compiler produces Scheme code, the code runs as fast as that produced by the previous action compilers.
- 1 January 1996
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 6 (2) , 269-298
Generating action compilers by partial evaluation
Compiler generation based on Mosses' action semantics has been studied by Brown, Moura, and Watt, and also by the second author. The core of each of their systems is a handwritten action compiler, producing either C or machine code. We have obtained an action compiler in a much simpler way: by partial evaluation of an action interpreter. Even though our compiler produces Scheme code, the code runs as fast as that produced by the previous action compilers.
- 1 September 1995
- Published by Springer Nature in Higher-Order and Symbolic Computation
- Vol. 8 (3) , 209-227
The essence of eta-expansion in partial evaluation
- 1 September 1995
- Published by Springer Nature in Higher-Order and Symbolic Computation
- Vol. 8 (3) , 209-227
The essence of eta-expansion in partial evaluation
- 1 September 1995
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 5 (3) , 419-429
Strong normalization with non-structural subtyping
We study a type system with a notion of subtyping that involves a largest type ⊤, a smallest type ⊥, atomic coercions between base types, and the usual ordering of function types. We prove that any λ-term typable in this system is strongly normalizing, which solves an open problem of Thatte. We also prove that the fragment without ⊥ types has strictly fewer terms. This demonstrates that ⊥ adds power to a type system.
- 1 September 1995
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 5 (3) , 419-429
Strong normalization with non-structural subtyping
We study a type system with a notion of subtyping that involves a largest type ⊤, a smallest type ⊥, atomic coercions between base types, and the usual ordering of function types. We prove that any λ-term typable in this system is strongly normalizing, which solves an open problem of Thatte. We also prove that the fragment without ⊥ types has strictly fewer terms. This demonstrates that ⊥ adds power to a type system.
- 1 September 1995
- Published by Wiley in Software: Practice and Experience
- Vol. 25 (9) , 975-995
Type inference of SELF: Analysis of objects with dynamic and multiple inheritance
- 1 September 1995
- Published by Wiley in Software: Practice and Experience
- Vol. 25 (9) , 975-995
Type inference of SELF: Analysis of objects with dynamic and multiple inheritance
- 11 June 1995
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 2 (41)
Eta-Expansion Does The Trick
Partial-evaluation folklore has it that massaging one's source programs can make them specialize better. In Jones, Gomard, and Sestoft's recent textbook, a whole chapter is dedicated to listing such "binding-time improvements'': non-standard use of continuation-passing style, eta-expansion, and a popular transformation called "The Trick''. We provide a unified view of these binding-time improvements, from a typing perspective. Just as a proper treatment of product values in partial evaluation requires partially static values, a proper treatment of disjoint sums requires moving static contexts across dynamic case expressions. This requirement precisely accounts for the non-standard use of continuation-passing style encountered in partial evaluation. In this setting, eta-expansion acts as a uniform binding-time coercion between values and contexts, be they of function type, product type, or disjoint-sum type. For the latter case, it achieves "The Trick''. In this paper, we extend Gomard and Jones's partial evaluator for the lambda-calculus, lambda-Mix, with products and disjoint sums; we point out how eta-expansion for disjoint sums does The Trick; we generalize our earlier work by identifying that eta-expansion can be obtained in the binding-time analysis simply by adding two coercion rules; and we specify and prove the correctness of our extension to lambda-Mix. See revised version BRICS-RS-96-17.
- 11 June 1995
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 2 (41)
Eta-Expansion Does The Trick
Partial-evaluation folklore has it that massaging one's source programs can make them specialize better. In Jones, Gomard, and Sestoft's recent textbook, a whole chapter is dedicated to listing such "binding-time improvements'': non-standard use of continuation-passing style, eta-expansion, and a popular transformation called "The Trick''. We provide a unified view of these binding-time improvements, from a typing perspective. Just as a proper treatment of product values in partial evaluation requires partially static values, a proper treatment of disjoint sums requires moving static contexts across dynamic case expressions. This requirement precisely accounts for the non-standard use of continuation-passing style encountered in partial evaluation. In this setting, eta-expansion acts as a uniform binding-time coercion between values and contexts, be they of function type, product type, or disjoint-sum type. For the latter case, it achieves "The Trick''. In this paper, we extend Gomard and Jones's partial evaluator for the lambda-calculus, lambda-Mix, with products and disjoint sums; we point out how eta-expansion for disjoint sums does The Trick; we generalize our earlier work by identifying that eta-expansion can be obtained in the binding-time analysis simply by adding two coercion rules; and we specify and prove the correctness of our extension to lambda-Mix. See revised version BRICS-RS-96-17.
- Open Access
- 1 September 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (455)
Complexity Results for 1-safe Nets
We study the complexity of several standard problems for 1-safe Petri nets and some of its subclasses. We prove that reachability, liveness, and deadlock are all PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-complete for free-choice nets and for 1-safe free-choice nets. Finally, we prove that for arbitrary Petri nets, deadlock is equivalent to reachability and liveness. This paper is to be presented at FST & TCS, Foundations of Software Technology & Theoretical Computer Science, to be held 15-17 December 1993, in Bombay, India. A version of the paper with most proofs omitted is to appear in the proceedings.
- 1 September 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (455)
Open AccessComplexity Results for 1-safe Nets
We study the complexity of several standard problems for 1-safe Petri nets and some of its subclasses. We prove that reachability, liveness, and deadlock are all PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-complete for free-choice nets and for 1-safe free-choice nets. Finally, we prove that for arbitrary Petri nets, deadlock is equivalent to reachability and liveness. This paper is to be presented at FST & TCS, Foundations of Software Technology & Theoretical Computer Science, to be held 15-17 December 1993, in Bombay, India. A version of the paper with most proofs omitted is to appear in the proceedings.
- Open Access
- 1 April 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (436)
Type Inference of SELF: Analysis of Objects with Dynamic and Multiple Inheritance
We have designed and implemented a type inference algorithm for the full SELF language. The algorithm can guarantee the safety and disambiguity of message sends, and provide useful information for browsers and optimizing compilers.
- 1 April 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (436)
Open AccessType Inference of SELF: Analysis of Objects with Dynamic and Multiple Inheritance
We have designed and implemented a type inference algorithm for the full SELF language. The algorithm can guarantee the safety and disambiguity of message sends, and provide useful information for browsers and optimizing compilers.
- 1 July 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (405)
Efficient Recursive Subtyping
Subtyping in the presence of recursive types for the lambda-calculus was studied by Amadio and Cardelli in 1991. They showed that the problem of deciding whether one recursive type is a subtype of another is decidable in exponential time.In this paper we give an O(n^2) algorithm. Our algorithm is based on a simplification of the definition of the subtype relation, which allows us to reduce the problem to the emptiness problem for a certain finite automaton with quadratically many states.It is known that equality of recursive types and the covariant Böhm order can be decided efficiently by means of finite automata. Our results extend the automata-theoretic approach to handle orderings based on contravariance.
- 1 July 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (405)
Efficient Recursive Subtyping
Subtyping in the presence of recursive types for the lambda-calculus was studied by Amadio and Cardelli in 1991. They showed that the problem of deciding whether one recursive type is a subtype of another is decidable in exponential time.In this paper we give an O(n^2) algorithm. Our algorithm is based on a simplification of the definition of the subtype relation, which allows us to reduce the problem to the emptiness problem for a certain finite automaton with quadratically many states.It is known that equality of recursive types and the covariant Böhm order can be decided efficiently by means of finite automata. Our results extend the automata-theoretic approach to handle orderings based on contravariance.
- Open Access
- 1 July 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (404)
Safety Analysis versus Type Inference for Partial Types
Safety analysis is an algorithm for determining if a terin in an untyped lambda calculus with constants is safe, i.e., if it does not cause an error during evaluation. We prove that safety analysis accepts strictly more safe lambda terms than does type inference for Thatte's partial types.
- 1 July 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (404)
Open AccessSafety Analysis versus Type Inference for Partial Types
Safety analysis is an algorithm for determining if a terin in an untyped lambda calculus with constants is safe, i.e., if it does not cause an error during evaluation. We prove that safety analysis accepts strictly more safe lambda terms than does type inference for Thatte's partial types.
- Open Access
- 1 April 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (394)
Efficient Inference of Partial Types
Partial types for the lambda-calculus were introduced by Thatte in 1988 as a means of typing objects that are not typable with simple types, such as heterogeneous lists and persistent data In that paper he showed that type inference for partial types was semidecidable. Decidability remained open until quite recently, when O'Keefe and Wand gave an exponential time algorithm for type inference.In this paper we give an O(n^3) algorithm. Our algorithm constructs a certain finite automaton that represents a canonical solution to a given set of type constraints. Moreover, the construction works equally well for recursive types; this solves an open problem stated by O'Keefe and Wand.
- 1 April 1992
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 21 (394)
Open AccessEfficient Inference of Partial Types
Partial types for the lambda-calculus were introduced by Thatte in 1988 as a means of typing objects that are not typable with simple types, such as heterogeneous lists and persistent data In that paper he showed that type inference for partial types was semidecidable. Decidability remained open until quite recently, when O'Keefe and Wand gave an exponential time algorithm for type inference.In this paper we give an O(n^3) algorithm. Our algorithm constructs a certain finite automaton that represents a canonical solution to a given set of type constraints. Moreover, the construction works equally well for recursive types; this solves an open problem stated by O'Keefe and Wand.