Topic: reduction languages

topics > computer science > programming > Group: types of programming languages

definition languages
evaluation in an environment
expression language
formal methods and languages
function application
functional programming
higher-order functions and combinators
lambda calculus
no need for replacement
no need for variables
reduction machines
referential transparency
semantics by an abstract machine
string transformation languages
symbolic manipulation of formulas
procedures as data


Reduction languages, or functional programming, are based on reduction machines. They are made of expressions containing atoms, applications, sequences and 'undefined'. They include a semantic function which reduces expressions in the reduction language. This semantic function is the formal definition of the reduction machine, and may itself be defined by a functional form. Its atoms are the primitive functions of the language. The simplest reduction language is arithmetic expressions applied to constants. For instance the expression '1+(2*3) is reduced to 1+(6), then to 1+6, then to 7. String transformation languages are similar to reduction languages.

Advantages--An expression's meaning is defined by the language. Programs in the language are the same as data. Many language constructs are no longer needed, e.g., variables, pointers, control structures, declarations and state machines. (cbb 5/80)

Subtopic: meaning as reduction up

Quote: in a purely applicative language, function application to known arguments always produces the same result; same for expression evaluation [»reynJC8_1972]
Quote: a primary language has a transition function which when repeatedly applied to a formula yields a formula that is its meaning [»backJ_1972]
Quote: the meaning of an FFP application x:y is the meaning of the result of applying the function represented by x to y [»backJ8_1978a]
Quote: in a closed applicative language, the meaning of an application (.mu. * ap [e,f]) is .mu.*[.rho. .mu. e].mu.f [»backJ_1973, OK]
Quote: the semantics of a reduction language specify the meaning of a program as another program; e.g., Landin's AEs [»backJ_1972]
Quote: a language is a mapping between expressions and a domain of discourse; if a function, the meaning of an expression is its consequent [»backJ_1973, OK]
Quote: reduction in lambda calculus is like eliminating differentiation in the differential calculus [»wegnP10_1986]
QuoteRef: knutDE6_1968 ;;132 each semantic rule is a mapping from component values to one value

Subtopic: meaning as fixed point up

Quote: defines semantics of FFP systems by the least fixed point operator; determines value given an expression [»backJ8_1978a]
Quote: complete language <=> fixed points of a semantic function are the values of its expressions [»backJ_1973, OK]

Subtopic: partial evaluation up

Quote: function application and expression evaluation may never produce a result; never terminates or stops with an error [»reynJC8_1972]

Subtopic: examples up

QuoteRef: backJ_1972 ;;25 arithmetic expression on constants are reduction languages
Quote: Red languages differ by having different atoms or different primitive functions represented by atoms [»backJ_1973]
Quote: an applicative expression consists of lambda expressions, operator applications, and expression lists; a fundamental notation [»landPJ1_1964]
QuoteRef: backJ_1973 ;;76 Red language with 4 types of expressions-atoms, applications sequences (el, e2, e3...) and undefined .bottom.
Quote: a functional program for matrix multiply is hierarchically constructed from simpler components; without word-at-a-time programming [»backJ8_1978a]
Quote: a functional program for matrix multiply contains no variables, no loops, no control statements, no initializations, no declarations

Related Topics up

Topic: definition languages (3 items)
Topic: evaluation in an environment (35 items)
Topic: expression language (14 items)
Topic: formal methods and languages (53 items)
Topic: function application (18 items)
Topic: functional programming (45 items)
Topic: higher-order functions and combinators (19 items)
Topic: lambda calculus (16 items)
Topic: no need for replacement (4 items)
Topic: no need for variables (13 items)
Topic: reduction machines (14 items)
Topic: reductionism (51 items)
Topic: referential transparency (26 items)
Topic: semantics by an abstract machine (38 items)
Topic: string transformation languages (17 items)
Topic: symbolic manipulation of formulas (12 items)
Topic: procedures as data
(22 items)

Updated barberCB 12/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.