Browsing by Author "Van Wyk, Eric"

Now showing 1 - 20 of 45

A Formal Approach to Parallelizing Compilers
(1997) Rus, Teodor; Van Wyk, Eric
This paper describes parallelizing compilers which allow programmers to tune parallel program performance through an interactive dialog. Programmers specify language constructs that define sequential processes, such as assignment or for-loops, to be used as units of computation, while the compiler discovers the parallelism existent in the source program in terms of these units. Programmers may provide target machine architectural features used by compilers to coalesce sequential processes, controlling process granularity and ensuring process load balance.
ableC: Extensible Specification of C Using the Silver Attribute Grammar System
(2017-08-24) Kaminski, Ted; Kramer, Lucas; Carlson, Travis; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools Group
This is the Silver specification of ableC: a specification of C at the ISO C11 standard. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.
Adding Dimension Analysis to Java as a Composable Language Extension
(Springer-Verlag, 2008) Van Wyk, Eric; Mali, Yogesh
In this paper we describe a language extension that adds dimension analysis to Java. Dimension analysis can be used to check that values that represent physical measurements such as length and mass are not used inconsistently. What distinguishes this work from previous work that adds dimension analysis to programming languages is that here the extension is implemented as a composable language extension. This means that it can easily be combined with other extensions, possibly developed by other parties, to create an extended implementation of Java with new features that address concerns from several different domains.
Adding Syntax and Static Analysis to Libraries via Extensible Compilers and Language Extensions
(2006) Van Wyk, Eric; Bodin, Derek; Huntington, Paul
We show how new syntactic forms and static analysis can be added to a programming language to support abstractions provided by libraries. Libraries have the important characteristic that programmers can use multiple libraries in a single program. Thus, any attempt to extend a language's syntax and analysis should be done in a composable manner so that similar extensions that support other libraries can be used by the programmer in the same program. To accomplish this we have developed an extensible attribute grammar specification of Java 1.4 written in the attribute grammar specification language Silver. Library writers can specify, as an attribute grammar, new syntax and analysis that extends the language and supports their library. The Silver tools automatically compose the grammars defining the language and the programmer-selected language extensions (for their chosen libraries) into a specification for a new custom language that has language-level support for the libraries. We demonstrate how syntax and analysis are added to a language by extending Java with syntax from the query language SQL and static analysis of these constructs so that syntax and type errors in SQL queries can be detected at compile-time.
Algebraic Implementation of Model Checking
(1996) Rus, Teodor; Van Wyk, Eric
We describe an algebraic methodology for implementing model checking algorithms. In this methodology temporal logic formulas are seen as phrases of a source language L_s and the sets of states of a the associated model are seen as elements of an algebra of sets called the target language, L_t. Thus, the model checker becomes an algebraic compiler C : L_s -> L_t which maps temporal logic formulas in L_s into the sets of states of the model in L_t which satisfy these formulas. Since algebraic compilers can be automatically generated from algebraic specifications of the source and target algebras this methodology enjoys the advantage of the automatic generation of model checking algorithms from the algebraic specification of the temporal logics and their associated models. Also, since algebraic compilers implement translation via a homomorphism between the source and target algebras, which is a naturally parallel computation, the model checkers thus implemented are naturally parallel algorithms.
An Algebraic Language Processing Environment
(1997) Rus, Teodor; Halverson, Tom; Van Wyk, Eric; Kooima, Robert
An Overview of XRobots: A Hierarchical State Machine-Based Language
(2011) Tousignant, Steve; Van Wyk, Eric; Gini, Maria
This paper introduces a prototype domain-specific language for programming mobile robots that is based on hierarchical state machines. A novelty of this language is that states are treated as first class entities in the language and thus they can be passed as arguments to other parameterized states. The structure and behavior of the language is presented, along with an example program. Further work and language design challenges are also discussed.
Attribute Grammar-based Language Extensions for Java
(2007) Van Wyk, Eric; Krishnan, Lijesh; Schwerdfeger, August; Bodin, Derek
This paper describes the Java Language Extender framework, a tool that allows one to create new domain-adapted languages by importing domain-specific language extensions into an extensible implementation of Java 1.4. Language extensions may define the syntax, semantic analysis, and optimizations of new language constructs. Java and the language extensions are specified as higher-order attribute grammars. We describe several language extensions and their implementation in the framework. For example, one embeds the SQL database query language into Java and statically checks for syntax and type errors in SQL queries.The tool supports the modular specification of composable language extensions so that programmers can import into Java the unique set of extensions that they desire. When extensions follow certain restrictions, they can be composed without requiring any implementation-level knowledge of the language extensions. The tools automatically compose the selected extensions and the Java host language specification.
Building Extensible Specifications and Implementations of Promela with AbleP
(Springer Verlag, 2011) Mali, Yogesh; Van Wyk, Eric
This paper describes how new language features can be seamlessly added to an extensible specification of Promela to provide new (domain-specific) notations and analyses to the engineer. This is accomplished using ableP, an extensible specification and implementation of Promela, the modeling language used by the SPIN model checker. Language extensions described here include an enhanced select-statement, a convenient tabular notation for boolean expressions, a notion of discrete time, and extended type checking. ableP and the extensions are developed using the Silver attribute grammar system and the Copper parser and scanner generator. These tools support the modular development and composition of language extensions so that independently developed extensions can be imported into ableP by an engineer with little knowledge of language design and implementation issues.
Compiler Optimization Correctness by Temporal Logic
(2004) Lacey, David; D. Jones, Neil; Van Wyk, Eric; Christian Frederiksen, Carl
Rewrite rules with side conditions can elegantly express many classical compiler optimizations for imperative programming languages. In this paper, programs are written in an intermediate language and transformation-enabling side conditions are specified in a temporal logic suitable for describing program data flow. The purpose of this paper is to show how such transformations may be proven correct. Our methodology is illustrated by three familiar optimizations: dead code elimination, constant folding, and code motion. A transformation is correct if whenever it can be applied to a program, the original and transformed programs are semantically equivalent, i.e., they compute the same input-output function. The proofs of semantic equivalence inductively show that a transformation-specific bisimulation relation holds between the original and transformed program computations.
Composable Language Extensions for Computational Geometry: a Case Study
(2007) Van Wyk, Eric; Johnson, Eric
In model-based development, a formal description of the software (the model) is the central artifact that drives other development activities. The availability of a modeling language well-suited for the system under development and appropriate tool support are of utmost importance to practitioners. Considering the diverse needs of different application domains, flexibility in the choice of modeling languages and tools may advance the industrial acceptance of formal methods. We describe a flexible modeling language framework by which language and tool developers may better meet the special needs of various users groups without incurring prohibitive costs. The framework is based on a modular and extensible implementation of languages features using attribute grammars and forwarding. We show a prototype implementation of such a framework by extending the host language Mini-Lustre, an example synchronous data-flow language, with a collection of features such as state transitions, condition tables, and events. We also show how new languages can be created in this framework by feature composition.
Context Aware Scanning: Specification, Implementation, and Applications
(2007-04-25) Van Wyk, Eric; Schwerdfeger, August
This report introduces new parsing and context-aware scanning algorithms in which the scanner uses contextual information to disambiguate lexical syntax. The parser utilizes a slightly modified LR-style algorithm that passes to the scanner the set of valid symbols which the scanner may return at that point in parsing. This set is the terminal symbols that are valid for the current state, i.e., those whose entry in the parse table are shift, reduce, or accept, but not error. The scanner then only returns tokens in this set. Also, an analysis is given that can statically verify that the scanner will never return more than one token for a single input. Context-aware scanning is especially useful when parsing and scanning extensible languages in which domain specific languages can be embedded. We illustrate this approach with a declarative specification of a Java subset and extensions that embed SQL queries and Boolean expression tables into Java. An updated version of this paper has been published in GPCE 2007. This version can be found at http://www.cs.umn.edu/~evw/papers.
Context in Parsing: Techniques and Applications
(Schloss Dagstuhl, 2023-04) Van Wyk, Eric
This paper discusses two approaches to parsing: Eelco Visser's scannerless generalized LR parsing and our context-aware scanning paired with deterministic LR parsing. We compare the underlying techniques, specifically how parser context is used to disambiguate lexical syntax, and their use in the context of language evolution and composition applications. We also reflect on the many discussions shared with Eelco on these topics, and on our shared realization that our different assumptions about the contexts in which our approaches were used drove and justified the technical decisions made in each.
Context-Aware Scanning for Parsing Extensible Languages
(2007) Van Wyk, Eric; Schwerdfeger, August
This paper introduces new parsing and context-aware scanning algorithms in which the scanner uses contextual information to disambiguate lexical syntax. The parser utilizes a slightly modified LR-style algorithm that passes to the scanner the set of valid symbols which the scanner may return at that point in parsing. This set is the terminal symbols that are valid for the current state, i.e., those whose entry in the parse table are shift, reduce, or accept, but not error. The scanner then only returns tokens in this set. Also, an analysis is given that can statically verify that the scanner will never return more than one token for a single input. Context-aware scanning is especially useful when parsing and scanning extensible languages in which domain specific languages can be embedded. We illustrate this approach with a declarative specification of a Java subset and extensions that embed SQL queries and Boolean expression tables into Java.
Extending Lustre with Timeout Automata
(2007) Gao, Jimin; Whalen, Michael; Van Wyk, Eric
This paper describes an extension to Lustre to support the analysis of globally asynchronous, locally synchronous (GALS) architectures. This extension consists of constructs for directly specifying the timeout automata used to describe asynchronous communication between processes represented by Lustre nodes. It is implemented using an extensible language framework based on attribute grammars that allows such extensions to be modularly defined so that they may be more easily composed with other language extensions.
Flexibility in Modeling Languages and Tools: A Call to Arms
(Springer-Verlag, 2009) Van Wyk, Eric; Heimdahl, Mats
In model-based development, the software development effort is centered around a formal description of the proposed software system; a description that can be subjected to various types of analysis and code generation. Based on years of experience with model-based development and formal modeling we believe that the following conjectures describe fundamental obstacles to wide adoption of formal modeling and the potential for automation that comes with it; (1) no single modeling notation will suit all, or even most, modeling needs, (2) no analysis tool will fit all, or even most, analysis tasks, and (3) flexible and stable tools must be made available for realistic evaluations and technology transfer. These conjectures form the basis for the call to arms outlined in this report. To make automated software engineering techniques more useful for more types of developers and allow us to move forward as a community it is crucial that we develop the foundation for building extensible and flexible modeling language processing tools. New common-infrastructure-based approaches are needed as traditional approaches based on file-based processing of intermediate language representations are not adequate. In this report we outline and illustrate the problem and discuss a possible solution. To initiate the discussions in the community, we hypothesize that languages and tools built using higher-order attribute grammars with forwarding can serve as a basis for such flexible language processing tools; tools that will allow us to unify our efforts and help bring our collective work to a broader audience.
Flexible and Extensible Notations for Modeling Languages
(2007) Gao, Jimin; Heimdahl, Mats; Van Wyk, Eric
In model-based development, a formal description of the software (the model) is the central artifact that drives other development activities. The availability of a modeling language well-suited for the system under development and appropriate tool support are of utmost importance to practitioners. Considering the diverse needs of different application domains, flexibility in the choice of modeling languages and tools may advance the industrial acceptance of formal methods. We describe a flexible modeling language framework by which language and tool developers may better meet the special needs of various users groups without incurring prohibitive costs. The framework is based on a modular and extensible implementation of languages features using attribute grammars and forwarding. We show a prototype implementation of such a framework by extending the host language Mini-Lustre, an example synchronous data-flow language, with a collection of features such as state transitions, condition tables, and events. We also show how new languages can be created in this framework by feature composition.
Forwarding in Attribute Grammars for Modular Language Design
(2002) Van Wyk, Eric; de Moor, Oege; Backhouse, Kevin; Kwiatkowsky, Paul
Forwarding is a technique for providing default attribute definitions in attribute grammars that is helpful in the modular implementation of programming languages. It complements existing techniques such as default copy rules. This paper introduces forwarding, and shows how it is but a small extension of standard higher-order attribute grammars. The usual tools for manipulating higher-order attribute grammars, including the circularity check (which tests for cyclic dependencies between attribute values), carry over without modification. The closure test (which checks that each attribute has a defining equation) needs modification, however, because the resulting higher-order attribute grammars may contain spurious attributes that are never evaluated, and indeed that need not be defined.
From Models to Efficient Code: It's All in the Middle.
(2004) Van Wyk, Eric; Heimdahl, Mats; Saad, Yousef
An implementation of the lambda calculus in Silver
(2020-04-06) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools Group
This repository contains an implementation of the lambda calculus that uses the reflection-based term-rewriting extension to Silver. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.

University Digital Conservancy

Browse by Author

Browsing by Author "Van Wyk, Eric"