|
Supercompilation
Metacompilation is a computation which involves metasystem transitions (MST) from a computing machine ''M'' to a metamachine ''M' '' which controls, analyzes and imitates the work of ''M''. Semantics-based program transformation, such as partial evaluation and supercompilation (SCP), is metacomputation. Metasystem transitions may be repeated, as when a program transformer gets transformed itself. In this manner MST hierarchies of any height can be formed. The Fox paper reviews one strain of research which was started in Russia by Valentin Turchin's REFAL system in the late 1960s-early 1970s and became known for the development of supercompilation as a distinct method of program transformation. After a brief description of the history of this research line, the paper concentrates on those results and problems where supercompilation is combined with repeated metasystem transitions. See also *Metacompiler *Partial evaluation In computing, partial evaluation is a technique for sev ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Valentin Turchin
Valentin Fyodorovich Turchin (russian: Валенти́н Фёдорович Турчи́н, 14 February 1931 in Podolsk – 7 April 2010 in Oakland, New Jersey) was a Soviet and American physicist, cybernetician, and computer scientist. He developed the Refal programming language, the theory of metasystem transitions and the notion of supercompilation. He was as a pioneer in artificial intelligence and a proponent of the global brain hypothesis. Biography Turchin was born in 1931 in Podolsk, Soviet Union. In 1952, he graduated from Moscow University in Theoretical Physics, and got his Ph.D. in 1957. After working on neutron and solid-state physics at the Institute for Physics of Energy in Obninsk, in 1964 he accepted a position at the Keldysh Institute of Applied Mathematics in Moscow. There he worked in statistical regularization methods and authored REFAL, one of the first AI languages and the AI language of choice in the Soviet Union. In the 1960s, Turchin became politic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm). Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An especially well-known discipline of the study of computation is computer science. Physical process of Computation Computation can be seen as a purely physical process occurring inside a closed physical system called a computer. Examples of such physical systems are digital computers, mechanical computers, quantum computers, DNA computers, molecular computers, microfluidics-based computers, analog computers, and wetware computers. This point of view has been adopted by the physics of computation, a branch of theoretical physics, as well as the field of natural computing. An even more radical point of view, pancomputationalism (inaudible word), is the postulate of digital physics that argues that the evolution of the universe is itself ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metasystem
Meta-systems have several definitions. In general, they link the concepts " system" and "meta-". A "meta-system" is about other systems, such as describing, generalizing, modelling, or analyzing the other system(s). According to Turchin and Joslyn (1997), this "natural" systemic definition is not sufficient for their Theory of Meta-system Transition, it also is not equivalent to the definition of ''system of systems'' in Autopoietic Systems Theory. In economics In economics, meta-systems are like what Bataille calls general economies as opposed to the restricted economies of systems. In mathematics, biology and psychology In mathematics, biology and psychology, many variables have occurred within structures and systems that determined the results, discoveries, rates and value(s) of sets, systems, and developments within systems, structures, systems within structures and sets of structures. A mathematical-modelling rule system for a domain D is an example of a meta-syste ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semantic
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and computer science. History In English, the study of meaning in language has been known by many names that involve the Ancient Greek word (''sema'', "sign, mark, token"). In 1690, a Greek rendering of the term ''semiotics'', the interpretation of signs and symbols, finds an early allusion in John Locke's ''An Essay Concerning Human Understanding'': The third Branch may be called [''simeiotikí'', "semiotics"], or the Doctrine of Signs, the most usual whereof being words, it is aptly enough termed also , Logick. In 1831, the term is suggested for the third branch of division of knowledge akin to Locke; the "signs of our knowledge". In 1857, the term ''semasiology'' (borrowed from German ''Semasiologie'') is attested in Josiah W. Gibbs' '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partial Evaluation
In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs that run faster than the originals while being guaranteed to behave in the same way. A computer program ''prog'' is seen as a mapping of input data into output data: : prog : I_\text \times I_\text \to O, where I_\text, the ''static data'', is the part of the input data known at compile time. The partial evaluator transforms \langle prog, I_\text\rangle into prog^* : I_\text \to O by precomputing all static input at compile time. prog^* is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" prog to prog^*. Futamura projections A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura, is when ''prog'' is an interpreter for a programming languag ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Russia
Russia (, , ), or the Russian Federation, is a List of transcontinental countries, transcontinental country spanning Eastern Europe and North Asia, Northern Asia. It is the List of countries and dependencies by area, largest country in the world, with its internationally recognised territory covering , and encompassing one-eighth of Earth's inhabitable landmass. Russia extends across Time in Russia, eleven time zones and shares Borders of Russia, land boundaries with fourteen countries, more than List of countries and territories by land borders, any other country but China. It is the List of countries and dependencies by population, world's ninth-most populous country and List of European countries by population, Europe's most populous country, with a population of 146 million people. The country's capital and List of cities and towns in Russia by population, largest city is Moscow, the List of European cities by population within city limits, largest city entirely within E ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
REFAL
Refal ("Recursive functions algorithmic language"; russian: РЕФАЛ) "is a functional programming language oriented toward symbolic computations", including " string processing, language translation, ndartificial intelligence". It is one of the oldest members of this family, first conceived of in 1966 as a theoretical tool, with the first implementation appearing in 1968. Refal was intended to combine mathematical simplicity with practicality for writing large and sophisticated programs. One of the first functional programming languages to do so, and unlike Lisp of its time, Refal is based on pattern matching. Its pattern matching works in conjunction with term rewriting. The basic data structure of Lisp and Prolog is a linear list built by cons operation in a sequential manner, thus with ''O(n)'' access to list's ''n''th element. Refal's lists are built and scanned from both ends, with pattern matching working for nested lists as well as the top-level one. In effect, the bas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Program Transformation
A program transformation is any operation that takes a computer program and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics and in fewer cases the transformations result in programs that semantically differ from the original in predictable ways. While the transformations can be performed manually, it is often more practical to use a program transformation system that applies specifications of the required transformations. Program transformations may be specified as automated procedures that modify compiler data structures (e.g. abstract syntax trees) representing the program text, or may be specified more conveniently using patterns or templates representing parameterized source code fragments. A practical requirement for source code transformation systems is that they be able to effectively process programs written in a programming language. This usually require ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metacompiler
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine. The most common type of compiler-compiler is more precisely called a parser generator. It only handles syntactic analysis. The input of a parser generator is a grammar file, typically written in Backus–Naur form (BNF) or extended Backus–Naur form (EBNF) that defines the syntax of a target programming language. The output is the source code of a parser for the programming language. The output of the (compiled) parser source code is a parser. It may be either standalone or embedded. This parser takes as an input the source code of the target programming language source and performs some action or outputs an abstract syntax tree (AST). Parser generators do not handle the semantics of the AST, or the generation of machine code for the target machine."A Syntax Directed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partial Evaluation
In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs that run faster than the originals while being guaranteed to behave in the same way. A computer program ''prog'' is seen as a mapping of input data into output data: : prog : I_\text \times I_\text \to O, where I_\text, the ''static data'', is the part of the input data known at compile time. The partial evaluator transforms \langle prog, I_\text\rangle into prog^* : I_\text \to O by precomputing all static input at compile time. prog^* is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" prog to prog^*. Futamura projections A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura, is when ''prog'' is an interpreter for a programming languag ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |