| 
|
Topic: reduction machines
topics >
computer science >
computer hardware >
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
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: combinators
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: variations
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]
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]
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)