Th Topic: reduction languages

Topic: reduction languages

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

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

Summary

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

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

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

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

Subtopic: examples

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

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)