1,721,073 research outputs found
Programming Languages shouldn't be "too Natural"
Full text linkDespite much research on programming language principles, most often
the design of modern languages ignores such principles which results in
cumbersome, hard to understand, and error-prone code. We substantiate
our claim through a short sampling of the features of some widely used
languages and by referring to other criticisms widely publicized in the
literature. We argue that a major reason of such an unpleasant state of
the art is that programming languages evolve in a way that too much
resembles that of natural languages. We advocate a different attitude in
programming language design, going back to essentiality and rigorous
application of few basic, well-chosen principles
A SAT-based parser and completer for pictures specified by tiling
No full textPictures or patterns have been formally specified by different methods such as grammars. An alternative approach is based on tiling systems
(TS) (Wang tiles are an analogous and equivalent formalism), whereby the picture is obtained by first covering it with a specified set of
2 × 2 tiles, then by performing a pixel by pixel mapping. TS are a powerful technique: the corresponding pictures can be recognized by
non-deterministic cellular automata, which are more powerful than the four-ways automata. The difficulty to write such specifications for nonelementary
pictures, and the NP-complete computational complexity of TS picture recognition have so far blocked any attempt to application.
We have implemented a recognizer and generator for TS pictures in a very attractive, unconventional way, by transforming the tiling problem
into a SAT (Boolean satisfiability) one, then using an efficient off-the-shelf SAT-solver. The prototype is fast enough to experiment on reasonably
sized samples, and has the bonus of being able to complete or extrapolate a partial or noisy picture. The tool is invaluable to assist in writing
picture specification. A series of examples shows how to specify patterns using TS
Regional Languages and Tiling: A Unifying Approach to Picture Grammars
No full textSeveral classical models of picture grammars based on array rewriting rules can be unified and extended by a tiling based approach. The right part of a rewriting rule is formalized by a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoney’s (or Matz’s) Kolam grammars, and their generalization by Prusa. Regionally defined pictures can be recognized with
polynomial time complexity by an algorithm extending the CKY one for strings.
Regional tile grammars and languages are strictly included into the tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang’s tilings)
ContextErlang: A language for distributed context-aware self-adaptive applications
Full text linkSelf-adaptive software modifies its behavior at run time to satisfy changing requirements in a dynamic environment. Context-oriented programming (COP) has been recently proposed as a specialized programming paradigm for context-aware and adaptive systems. COP mostly focuses on run time adaptation of the application’s behavior by supporting modular descriptions of behavioral variations. However, self-adaptive applications must satisfy additional requirements, such as distribution and concurrency, support for unforeseen changes and enforcement of correct behavior in the presence of dynamic change. Addressing these issues at the language level requires a holistic design that covers all aspects and takes into account the possibly cumbersome interaction of those features, for example concurrency and dynamic change. We present ContextErlang, a COP programming language in which adaptive abstractions are seamlessly integrated with distribution and concurrency. We define ContextErlang’s formal semantics, validated through an executable prototype, and we show how it supports formal proofs that the language design ensures satisfaction of certain safety requirements. We provide empirical evidence that ContextErlang is an effective solution through case studies and a performance assessment. We also show how the same design principles that lead to the development of ContextErlang can be followed to systematically design contextual extensions of other languages. A concrete example is presented concerning ContextScala
Tile rewriting grammars and picture languages
No full textTile Rewriting Grammars (TRG) are a new model for defining picture languages. A rewriting
rule changes a homogeneous rectangular subpicture into a isometric one tiled with
specified tiles. Derivation and language generation with TRG rules are similar to contextfree
grammars. A normal form and some closure properties are presented. We prove this
model has greater generative capacity than the Tiling Systems of Giammarresi and Restivo
and the grammars of Matz, another generalization of context free string grammars to 2D.
Examples are shown for pictures made by nested frames and spirals
Higher-order operator precedence languages
Full text linkFloyd's Operator Precedence (OP) languages are a deterministic context-free family having many desirable properties. They are locally and parallely parsable, and languages having a compatible structure are closed under Boolean operations, concatenation and star; they properly include the family of Visibly Pushdown (or Input Driven) languages. OP languages are based on three relations between any two consecutive terminal symbols, which assign syntax structure to words. We extend such relations to k-Tuples of consecutive terminal symbols, by using the model of strictly locally testable regular languages of order k ⥠3. The new corresponding class of Higher-order Operator Precedence languages (HOP) properly includes the OP languages, and it is still included in the deterministic (also in reverse) context free family. We prove Boolean closure for each subfamily of structurally compatible HOP languages. In each subfamily, the top language is called max-language. We show that such languages are defined by a simple cancellation rule and we prove several properties, in particular that max-languages make an infinite hierarchy ordered by parameter k. HOP languages are a candidate for replacing OP languages in the various applications where they have have been successful though sometimes too restrictive
- …
