|
E-graph
In computer science, an e-graph is a data structure that stores an equivalence relation over terms of some language. Definition and operations Let \Sigma be a set of uninterpreted functions, where \Sigma_n is the subset of \Sigma consisting of functions of arity n. Let \mathbb be a countable set of opaque identifiers that may be compared for equality, called e-class IDs. The application of f\in\Sigma_n to e-class IDs i_1, i_2, \ldots, i_n\in\mathbb is denoted f(i_1, i_2, \ldots, i_n) and called an e-node. The e-graph then represents equivalence classes of e-nodes, using the following data structures: * A union-find structure U representing equivalence classes of e-class IDs, with the usual operations \mathrm, \mathrm and \mathrm. An e-class ID e is canonical if \mathrm(U, e) = e; an e-node f(i_1,\ldots,i_n) is canonical if each i_j is canonical (j in 1,\ldots,n). * An association of e-class IDs with sets of e-nodes, called e-classes. This consists of ** a hashcons H (i.e. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, applied disciplines (including the design and implementation of Computer architecture, hardware and Software engineering, software). Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and preventing security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Abstract Syntax Tree
An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring in the text. It is sometimes called just a syntax tree. The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if-condition-then statement may be denoted by means of a single node with three branches. This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
LLVM
LLVM, also called LLVM Core, is a target-independent optimizer and code generator. It can be used to develop a Compiler#Front end, frontend for any programming language and a Compiler#Back end, backend for any instruction set architecture. LLVM is designed around a language-independent specification, language-independent intermediate representation (IR) that serves as a Software portability, portable, high-level assembly language that can be optimizing compiler, optimized with a variety of transformations over multiple passes. The name ''LLVM'' originally stood for ''Low Level Virtual Machine.'' However, the project has since expanded, and the name is no longer an acronym but an orphan initialism. LLVM is written in C++ and is designed for compile-time, Linker (computing), link-time, runtime (program lifecycle phase), runtime, and "idle-time" optimization. Originally implemented for C (programming language), C and C++, the language-agnostic design of LLVM has since spawned a wide ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Translation Validation
In computing, compiler correctness is the branch of computer science that deals with trying to show that a compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ... behaves according to its programming language, language specification. Techniques include developing the compiler using formal methods and using rigorous testing (often called compiler validation) on an existing compiler. Formal verification Two main formal verification approaches for establishing correctness of compilation are proving correctness of the compiler for all inputs and proving correctness of a compilation of a particular program (translation validation). Compiler correctness for all input programs Compiler validation with formal methods involves a long chain of formal, deductive logic. However, since ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
