Map Index Random Help Topics

## Topic: reduction machines

topics > computer science > computer hardware > Group: machine model

Group:
data value
Group:
expression evaluation

Topic:
block machines
Topic:
lambda calculus
Topic:
no need for variables
Topic:
primitive functions
Topic:
programming as mathematics
Topic:
procedures as data
Topic:
reduction languages
Topic:
sequence reduction
Topic:
state machine
Topic:
string transformation languages

#### Summary

A reduction machine takes an expression and successively reduces sub-expressions to their value until a unique expression is reached. This unique expression is the value of the original, since each reduction resulted in equivalent forms. The value depends on a set of basic application atoms associated with the machine. John Backus is the major proponent of reduction machines as a replacement for 'von Neumann' computers. By not having a state memory, reduction machines remove the expense of memory access.

Advantages--No dependence on 'von Neumann' machines, the machine has a formal, textual representation of its semantic function. (cbb 5/80)

Subtopic: reduction as primitive

 Quote: reduction is the atom of behavior of lambda-calculus; i.e., passing an argument to a function QuoteRef: backJ_1973 ;;72 RED languages are the Turing machines of programming languages but with sophisticated primitive operators become high-level

Subtopic: reduction

 Quote: reduce an expression by replacing a subexpression by its value; reduction language Quote: to reduce a formula, need to know how to reduce one of its simplest, non-constant subformulas [»backJ_1972] Quote: in an applicative language, replace components by their meaning; get meaning of whole unless it's an application [»backJ_1973] Quote: meaning of an FFP expression found by replacing innermost application with its meaning [»backJ8_1978a] Quote: in a closed applicative language, an expression is a constant (its own meaning) unless applied [»backJ_1973, OK] Quote: in a closed applicative language, all reductions terminate at the same meaning (if any) [»backJ_1973, OK]

Subtopic: combinators

 Quote: a machine for combinators reduces compiled code; unlike self-modifying code, it preserves meaning [»turnDA1_1979] Quote: use combinators to find the value of a financial contract; compositional, abstract valuation semantics [»joneSP9_2000]

Subtopic: variations

 Quote: a language has a state language when its domain is a set of computations that define the reduction operator [»backJ_1973] Quote: a complete realization defines a transition function and constants; can realize a complete language [»backJ_1973, OK] Quote: constructor syntax uses a set of constructors and atomic expressions to define non-atomic expressions [»backJ_1973, OK] Quote: SASL compiler produces a graph which the run-time system reduces to a number or other printable object [»turnDA1_1979]

Related Topics

Group: data value   (19 topics, 433 quotes)
Group: expression evaluation   (5 topics, 97 quotes)

Topic: block machines (8 items)
Topic: lambda calculus (16 items)
Topic: no need for variables (13 items)
Topic: primitive functions (34 items)
Topic: programming as mathematics (27 items)
Topic: procedures as data (22 items)
Topic: reduction languages (17 items)
Topic: sequence reduction (10 items)
Topic: state machine (67 items)
Topic: string transformation languages
(17 items)

Updated barberCB 12/04