| 1. |
- Almström Duregård, Jonas, 1984, et al.
(författare)
-
Embedded Parser Generators
- 2011
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 46:12, s. 107-117
-
Tidskriftsartikel (refereegranskat)abstract
- We present a novel method of embedding context-free grammars in Haskell, and to automatically generate parsers and pretty-printers from them. We have implemented this method in a library called BNFC-meta (from the BNF Converter, which it is built on). The library builds compiler front ends using metaprogramming instead of conventional code generation. Parsers are built from labelled BNF grammars that are defined directly in Haskell modules. Our solution combines features of parser generators (static grammar checks, a highly specialised grammar DSL) and adds several features that are otherwise exclusive to combinatory libraries such as the ability to reuse, parameterise and generate grammars inside Haskell. To allow writing grammars in concrete syntax, BNFC-meta provides a quasi-quoter that can parse grammars (embedded in Haskell files) at compile time and use metaprogramming to replace them with their abstract syntax. We also generate quasi-quoters so that the languages we define with BNFC-meta can be embedded in the same way. With a minimal change to the grammar, we support adding anti-quotation to the generated quasi-quoters, which allows users of the defined language to mix concrete and abstract syntax almost seamlessly. Unlike previous methods of achieving anti-quotation, the method used by BNFC-meta is simple, efficient and avoids polluting the abstract syntax types.
|
|
| 2. |
- Axelsson, Emil, 1978, et al.
(författare)
-
Using Circular Programs for Higher-Order Syntax Functional pearl
- 2013
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 48:9, s. 257-262
-
Tidskriftsartikel (refereegranskat)abstract
- This pearl presents a novel technique for constructing a first-order syntax tree directly from a higher-order interface. We exploit circular programming to generate names for new variables, resulting in a simple yet efficient method. Our motivating application is the design of embedded languages supporting variable binding, where it is convenient to use higher-order syntax when constructing programs, but first-order syntax when processing or transforming programs.
|
|
| 3. |
- Bernardy, Jean-Philippe, 1978, et al.
(författare)
-
Efficient Divide-and-Conquer Parsing of Practical Context-Free Languages
- 2013
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 48:9, s. 111-122
-
Tidskriftsartikel (refereegranskat)abstract
- We present a divide-and-conquer algorithm for parsing context-free languages efficiently. Our algorithm is an instance of Valiant's (1975), who reduced the problem of parsing to matrix multiplications. We show that, while the conquer step of Valiant's is O(n(3)) in the worst case, it improves to O(log (3) n), under certain conditions satisfied by many useful inputs. These conditions occur for example in program texts written by humans. The improvement happens because the multiplications involve an overwhelming majority of empty matrices. This result is relevant to modern computing: divide-and-conquer algorithms can be parallelized relatively easily.
|
|
| 4. |
- Bernardy, Jean-Philippe, 1978, et al.
(författare)
-
Parametricity and Dependent Types
- 2010
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 45:9, s. 345-356
-
Tidskriftsartikel (refereegranskat)abstract
- Reynolds' abstraction theorem shows how a typing judgement in System F can be translated into a relational statement (in second order predicate logic) about inhabitants of the type. We (in second order predicate logic) about inhabitants of the type. We obtain a similar result for a single lambda calculus (a pure type system), in which terms, types and their relations are expressed. Working within a single system dispenses with the need for an interpretation layer, allowing for an unusually simple presentation. While the unification puts some constraints on the type system (which we spell out), the result applies to many interesting cases, including dependently-typed ones.
|
|
| 5. |
- Bernardy, Jean-Philippe, 1978, et al.
(författare)
-
Type-Theory In Color
- 2013
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 48:9, s. 61-71
-
Tidskriftsartikel (refereegranskat)abstract
- Dependent type-theory aims to become the standard way to formalize mathematics at the same time as displacing traditional platforms for high-assurance programming. However, current implementations of type theory are still lacking, in the sense that some obvious truths require explicit proofs, making type-theory awkward to use for many applications, both in formalization and programming. In particular, notions of erasure are poorly supported.In this paper we propose an extension of type-theory with colored terms, color erasure and interpretation of colored types as predicates. The result is a more powerful type-theory: some definitions and proofs may be omitted as they become trivial, it becomes easier to program with precise types, and some parametricity results can be internalized.
|
|
| 6. |
- Broberg, Niklas, 1979, et al.
(författare)
-
Paralocks - Role-Based Information Flow Control and Beyond
- 2010
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 45:1, s. 431-444
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents Paralocks, a language for building expressive but statically verifiable fine-grained information flow policies. Paralocks combine the expressive power of Flow Locks (Broberg & Sands, ESOP'06) with the ability to express policies involving runtime principles, roles (in the style of role-based access control), and relations (such as "acts-for" in discretionary access control). We illustrate the Paralocks policy language by giving a simple encoding of Myers and Liskov's Decentralized Label Model (DLM). Furthermore - and unlike the DLM - we provide an information flow semantics for full Paralock policies. Lastly we illustrate how Paralocks can be statically verified by providing a simple programming language incorporating Paralock policy specifications, and a static type system which soundly enforces information flow security according to the Paralock semantics.
|
|
| 7. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2010
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 45:5, s. 339-340
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide are difficult to compose into larger atomic operations while still guaranteeing lock-freedom. We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 8. |
- Clarke, D., et al.
(författare)
-
Abstract Delta Modeling
- 2010
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 46:2, s. 13-22
-
Tidskriftsartikel (refereegranskat)abstract
- Delta modeling is an approach to facilitate automated product derivation for software product lines. It is based on a set of deltas specifying modifications that are incrementally applied to a core product. The applicability of deltas depends on feature-dependent conditions. This paper presents abstract delta modeling, which explores delta modeling from an abstract, algebraic perspective. Compared to previous work, we take a more flexible approach with respect to conflicts between modifications and introduce the notion of conflict-resolving deltas. We present conditions on the structure of deltas to ensure unambiguous product generation.
|
|
| 9. |
- Forsberg, Markus, 1974, et al.
(författare)
-
Functional Morphology
- 2004
-
Ingår i: SIGPLAN notices. - : Association for Computing Machinery (ACM). - 0362-1340 .- 1558-1160 .- 0730-8566. ; 39:9, s. 213-223
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents a methodology for implementing natural language morphology in the functional language Haskell. The main idea behind is simple: instead of working with untyped regular expressions, which is the state of the art of morphology in computational linguistics, we use finite functions over hereditarily finite algebraic datatypes. The definitions of these datatypes and functions are the language-dependent part of the morphology. The language-independent part consists of an untyped dictionary format which is used for synthesis of word forms, and a decorated trie, which is used for analysis. Functional Morphology builds on ideas introduced by Huet in his computational linguistics toolkit Zen, which he has used to implement the morphology of Sanskrit. The goal has been to make it easy for linguists, who are not trained as functional programmers, to apply the ideas to new languages. As a proof of the productivity of the method, morphologies for Swedish, Italian, Russian, Spanish, and Latin have already been implemented using the library. The Latin morphology is used as a running example in this article.
|
|
| 10. |
- Hughes, John, 1958
(författare)
-
Experiences from teaching functional programming at Chalmers
- 2008
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 43:11, s. 77-80
-
Tidskriftsartikel (refereegranskat)abstract
- John Hughes shared his experiences of teaching functional programming at Chalmers University in Gothenburg along with the successes and the problems he faced. His highest priority was to convince students that they could write real, interesting programs in Haskell by the end of the first course. He eliminated all the course material directly irrelevant to programming like a section on program proofs. He used to taught the material in a different order to most functional programming texts, like introducing Haskell input/output in the first lecture. He also included two lectures on GUI programming (using wxHaskell), building a simple straight-line-diagram editor in a couple of pages of code. He also introduced QuickCheck (random property-based) testing as part of the course, teaching students first to write the left-hand-side and type of a function, then its property, and finally its right-hand-side.
|
|
