TXL (programming language)
Encyclopedia
TXL is a special-purpose programming language
originally designed by Charles Halpern-Hamu and James Cordy
at the University of Toronto
in 1985. The acronym "TXL" originally stood for "Turing eXtender Language" after the language's original purpose, the specification and rapid prototyping
of variants and extensions of the Turing programming language, but no longer has any meaningful interpretation.
Modern TXL is specifically designed for creating, manipulating and rapidly prototyping language-based descriptions, tools and applications using source transformation. It is a hybrid functional
/ rule-based language using first order functional programming at the higher level and term rewriting at the lower level. The formal semantics and implementation of TXL are based on formal term rewriting, but the term structures are largely hidden from the user due to the example-like style of pattern specification.
Each TXL program has two components: a description of the source structures to be transformed, specified as a (possibly ambiguous) context-free grammar
using an extended Backus–Naur Form
; and a set of tree transformation rules, specified using pattern / replacement pairs combined using first order functional programming. TXL is designed to allow explicit programmer control over the interpretation, application, order and backtracking of both parsing and rewriting rules, allowing for expression of a wide range of grammar-based techniques such as agile parsing.
The first component parses the input expression into a tree using pattern-matching. The second component uses Term-rewriting in a manner similar to Yacc
to produce the transformed output.
TXL is most commonly used in software analysis and reengineering tasks such as design recovery
, and in rapid prototyping of new programming languages and dialects.
define program
[repeat number]
end define
%Transformation rules
rule main
replace $ [repeat number]
N1 [number] N2 [number] Rest [repeat number]
where
N1 [> N2]
by
N2 N1 Rest
end rule
define program
[number]
end define
%Transformation rules
function main
replace [program]
p [number]
by
p [fact][fact0]
end function
function fact
replace [number]
n [number]
construct nMinusOne [number]
n [- 1]
where
n [> 1]
construct factMinusOne [number]
nMinusOne [fact]
by
n [* factMinusOne]
end function
function fact0
replace [number]
0
by
1
end function
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
originally designed by Charles Halpern-Hamu and James Cordy
James Cordy
James Reginald Cordy, born , is a Canadian computer scientist and educator who is a Professor in the School of Computing at Queen's University. As a researcher he is currently active in the fields of source code analysis and manipulation, software reverse and re-engineering, and pattern analysis...
at the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
in 1985. The acronym "TXL" originally stood for "Turing eXtender Language" after the language's original purpose, the specification and rapid prototyping
Rapid prototyping
Rapid prototyping is the automatic construction of physical objects using additive manufacturing technology. The first techniques for rapid prototyping became available in the late 1980s and were used to produce models and prototype parts. Today, they are used for a much wider range of applications...
of variants and extensions of the Turing programming language, but no longer has any meaningful interpretation.
Modern TXL is specifically designed for creating, manipulating and rapidly prototyping language-based descriptions, tools and applications using source transformation. It is a hybrid functional
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
/ rule-based language using first order functional programming at the higher level and term rewriting at the lower level. The formal semantics and implementation of TXL are based on formal term rewriting, but the term structures are largely hidden from the user due to the example-like style of pattern specification.
Each TXL program has two components: a description of the source structures to be transformed, specified as a (possibly ambiguous) context-free grammar
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
using an extended Backus–Naur Form
Extended Backus–Naur form
In computer science, Extended Backus–Naur Form is a family of metasyntax notations used for expressing context-free grammars: that is, a formal way to describe computer programming languages and other formal languages. They are extensions of the basic Backus–Naur Form metasyntax notation.The...
; and a set of tree transformation rules, specified using pattern / replacement pairs combined using first order functional programming. TXL is designed to allow explicit programmer control over the interpretation, application, order and backtracking of both parsing and rewriting rules, allowing for expression of a wide range of grammar-based techniques such as agile parsing.
The first component parses the input expression into a tree using pattern-matching. The second component uses Term-rewriting in a manner similar to Yacc
Yacc
The computer program yacc is a parser generator developed by Stephen C. Johnson at AT&T for the Unix operating system. The name is an acronym for "Yet Another Compiler Compiler." It generates a parser based on an analytic grammar written in a notation similar to BNF.Yacc used to be available as...
to produce the transformed output.
TXL is most commonly used in software analysis and reengineering tasks such as design recovery
Reengineering (software)
The reengineering of software was described by Chikofsky and Cross in their 1990 paper, as "The examination and alteration of a system to reconstitute it in a new form"...
, and in rapid prototyping of new programming languages and dialects.
BubbleSorthttp://star.itc.it/ricca/swat/SORT/Sort.Txl
%Syntax specificationdefine program
[repeat number]
end define
%Transformation rules
rule main
replace $ [repeat number]
N1 [number] N2 [number] Rest [repeat number]
where
N1 [> N2]
by
N2 N1 Rest
end rule
Factorial http://star.itc.it/ricca/swatII/Esercizi/factorial.txl
%Syntax specificationdefine program
[number]
end define
%Transformation rules
function main
replace [program]
p [number]
by
p [fact][fact0]
end function
function fact
replace [number]
n [number]
construct nMinusOne [number]
n [- 1]
where
n [> 1]
construct factMinusOne [number]
nMinusOne [fact]
by
n [* factMinusOne]
end function
function fact0
replace [number]
0
by
1
end function
See also
- Turing (programming language)
- Refal (programming language)RefalRefal "is a functional programming language oriented toward symbol manipulation", including "string processing, translation, [and] artificial intelligence". It is one of the oldest members of this family, first conceived in 1966 as a theoretical tool with the first implementation appearing in 1968...
- DMS Software Reengineering ToolkitDMS Software Reengineering ToolkitThe DMS Software Reengineering Toolkit is a proprietary set of program transformation tools available for automating custom source program analysis, modification, translation or generation of software systems for arbitrary mixtures of source languages for large scale software systems.DMS has been...
- Program TransformationProgram transformationA 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...