1-4hit |
The Krivine-style evaluation mechanism is well-known in the implementation of higher-order functions, allowing to avoid some useless closure building. There have been a few type systems that can verify the safety of the mechanism. The incorporation of the proposed ideas into an existing compiler, however, would require significant changes in the type system of the compiler due to the use of some dedicated form of types and typing rules in the proposals. This limitation motivates us to propose an alternative light-weight Krivine typing mechanism that does not need to extend any existing type system significantly. This paper shows how GADTs (Generalized algebraic data types) can be used for typing a ZINC machine following the Krivine-style evaluation mechanism. This idea is new as far as we know. Some existing typed compilers like GHC (Glasgow Haskell compiler) already support GADTs; they can benefit from the Krivine-style evaluation mechanism in the operational semantics with no particular extension in their type systems for the safety. We show the GHC type checker allows to prove mechanically that ZINC instructions are well-typed, which highlights the effectiveness of GADTs.
Benjamin CARRION SCHAFER Yusuke IGUCHI Wataru TAKAHASHI Shingo NAGATANI Kazutoshi WAKABAYASHI
A methodology to automatically convert fixed point data type representations into integer data types for high level synthesis is presented in this work. Our method converts all major C operations using fixed point data types into integer data types, models quantization and overflow modes, type conversion and casting. The conversion rule for each operation is described in detail as well as a regression test environment with 600 test cases to validate the method and to verify the correctness of each conversion compared to the same cases written in SystemC. The test environment converts each test case with fixed point data types into integer data types and synthesizes them with a high level synthesis tool to generate RTL. An RTL simulation is ran and the results in turn compared to the SystemC's OSCI simulation. For all of the 600 test cases the RTL simulation results matched the SystemC results proving that each conversion is accurately modeled. A larger real test case is also presented to validate the conversion method in a complex case.
Masatoshi YOSHIKAWA Hiroyuki KATO Hiroko KINUTANI
Structured documents often contain character strings of which semantics can be naturally stored as database values or has direct correspondence with database values. By building bilateral logical links between character strings in documents and corresponding database values, semantically rich queries are made expressible. We have introduced a new ADT, named "paratext," to model text which has links with database values. Paratexts are logically viewed as consisting of two parallel layers; on the "appearance" layer, ordinary text (i. e. a linear sequence of character strings) is placed, while the "reference" layer holds an array of OIDs and literals. Each OID or literal on the reference layer is associated with a contiguous substring of the appearance layer text, and represents the semantics of the associated substring. We have also designed domain-specific functions for this document model. Using the functions, we can express queries which go back and forth between the two layers. In structured documents, such character strings can appear in the whole content of logical elements, or as phrases inside logical elements. We also present frameworks for the implementation of the paratext ADT, and discuss how traditional full-text indexing techniques can be extended to support paratext.
Yasunori ISHIHARA Atsushi OHSAKI Hiroyuki SEKI Tadao KASAMI
When a natural language specification is translated into a formal one, it is important for objects and operations appearing in the natural language specification to be appropriately classified according to the framework of data types in the formal specification. In this paper, we propose a semi-automatic method of constructing a context-free grammar (cfg) representing an assignment of data types to words in a given natural language specification. In our method, a cfg is mechanically constructed from sample sentences in a natural language specification, where the cfg represents type declarations of expressions and type hierarchy. Then, the cfg is appropriately modified by adding nonterminals/production rules that represent type inclusion relations. In this modification process, candidates for the productions to be added are presented to the user. Finally, the cfg is simplified based on structural equivalence. The result of applying this method to a part of the OSI session protocol specification (39 sentences) is also presented. There was an example in which ambiguity of anaphoric bindings was solved by type checking based on the resulting cfg.