Topic: reduction machines

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

data value
expression evaluation

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


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 up

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 up

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 up

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 up

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

Related Topics up

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
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.