Topic: functional programming

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

expression evaluation

curried functions
evaluation in an environment
expression language
formal methods and languages
function application
functional side effects
higher-order functions and combinators
incremental development
initialized constants
lambda calculus
no need for replacement
orthogonal extension and cartesian products
procedures as data
programming as mathematics
programming with a database of modules
reduction languages
referential transparency
sequence reduction
type algebras, typed lambda calculus, and type-complete languages
universal data type
problems with the von Neumann architecture


For instance Backus lambastes the incremental state modification used by computers Instead he would rather see the state as a data value, modified as a whole.
Subtopic: applicative expression up

Quote: an applicative expression consists of lambda expressions, operator applications, and expression lists; a fundamental notation [»landPJ1_1964]

Subtopic: program without side effects, assignment, gotos, or backtracking up

Quote: every program can be written as a recursive function without assignments or gotos [»dijkEW5_1965]
Quote: referential transparency--the result of a function is solely dependent on its arguments; a pure functional language [»plasR6_1999]
Quote: in a purely applicative language, function application to known arguments always produces the same result; same for expression evaluation [»reynJC8_1972]
Quote: a functional language needs substitutivity of equivalence for mathematical proofs about evaluations
Quote: a functional language prohibits all side effects; can draw if language output is a list of turtle commands [»wadlP2_1985]
Quote: for a language, define a functional subset without side effects; can be executed concurrently [»giffDK7_1985, OK]
Quote: functional programming further restricts logical statements by preventing the pursuit of irrelevant deductions [»hoarCA9_1987]
Quote: parallel arrays are Accelerator's fundamental data type; homogeneous, no index operator, no side effects; the result of any operation is a new array [»tardD10_2006]

Subtopic: modularity up

Quote: modularity through higher-order functions and lazy evaluation; shows examples in lists, trees, numerics, and AI [»hughJ_1984]
Quote: using functional programming, write alpha-beta evaluation as 'maximise . maptree static . prune 5 . gametree' [»hughJ_1984]

Subtopic: functional as explicit types up

Quote: in database query languages, queries produce new, implicit types; in functional programming every type is explicit [»wongL9_2000]
Quote: Kleisli and its self-describing data exchange use parametric polymorphism and type inference; from functional programming [»wongL9_2000]
Quote: the ext combinator is a universal construct for comprehensions and NRC; restricted form of structural recursion [»wongL9_2000]

Subtopic: object-oriented vs. functional up

Quote: object-oriented programming is the antithesis of functional programming; i.e., mutable object state vs. immutable, eternal values [»taivA4_1993]

Subtopic: bulk state transformations up

Quote: program semantics should not depend on baroque protocols for communicating with the state
Quote: a programming system should allow large state transformations by general functions [»backJ8_1978a]
Quote: updating a location is the same as producing a new store which is a slight modification of the original one [»straC3_1973]
Quote: a functional program for matrix multiply is hierarchically constructed from simpler components; without word-at-a-time programming [»backJ8_1978a]

Subtopic: data flow up

Quote: applicative languages are natural for data flow computation because all processing is operators applied to values [»ackeWB_1979]
Quote: in function-oriented programming, a process is a composition of functions on an input producing an output [»nygaK10_1986]

Subtopic: name equivalent to definition up

Quote: in FAD, the name for an item expression can always be replaced by its definition [»martJJ_1980]
Quote: in FP, a functional definition consists of a function name and a functional form that replaces the name [»backJ8_1978a]
Quote: all functions in an FP system map objects into objects; bottom-preserving, f.bottom. = .bottom. [»backJ8_1978a]
Quote: FAD functions map item expressions into themselves; gives formal definition for application; defines conditional [»martJJ_1980]

Subtopic: database of functions up

Quote: in FQL, a function can create a function; user can build a database of functions [»buneP1_1981]
Quote: in FQL, have a database of functions and a set of functionals that can operate on functions; e.g., extension and restriction [»buneP1_1981]

Subtopic: typed functional programming up

Quote: FAD deviates from Red by: encapsulation, data typing, sets of items, items vs. objects, naming, and infix operators [»martJJ_1980]
Quote: in FAD, an item expression denotes any finite set and certain infinite sets of items [»martJJ_1980]
Quote: in FAD, the item expression for a stack of integers is an infinite expression defined by recursion [»martJJ_1980]
Quote: a FAD object is a pair of items called the object's type and its value [»martJJ_1980]

Subtopic: typed assembly language up

Quote: translate an ML-like language into typed assembly language (TAL); proof carrying code [»morrG1_1998]
Quote: a typed assembly language enforces closures, tuples, and abstract data types without restricting low-level optimizations such as register allocation

Subtopic: simple functional languages up

Quote: create a purely functional language by removing unused features from Logo [»wadlP2_1985]
Quote: the simplest functional language $ uses one operator in two different ways: definition and application [»fehrE4_1983]
Quote: the simplest functional language $ only has evaluation by leftmost redex; not arbitrary replacement of subexpressions by value [»fehrE4_1983]
Quote: the functional language $ has one operator and a simple substitution rule [»specD1_1983]

Subtopic: examples of functional programming languages up

Quote: Vesta is a functional programming language for building systems [»heydA6_2000]
Quote: Vesta defines builds with a functional language, SDL (system description language); dynamically typed with closures and bindings; can be hard to understand [»heydA_2006]
Quote: used comprehension syntax and functional programming for the Kleisli data integration system; handles all popular bioinformatics systems [»wongL9_2000]

Subtopic: problems with time and space efficiency up

Quote: functional languages will evaluate both branches of 'and' even if they are the same; nasty practical problem [»joneSP9_2000]
Quote: optimization rule for vertical loop fusion in Kleisli [»wongL9_2000]
Quote: if response time and space requirements are important than applicative programming is less applicable [»morrJH_1980]

Subtopic: problems with functional programming up

Quote: a program is a sequence of steps even when represented as a functional form; e.g., nested functions and parameters [»wirtN1_1966]
Quote: simple programs become complex functional forms; assignments and jumps have complex representations

Related Topics up

Group: expression evaluation   (5 topics, 97 quotes)
Group: function   (12 topics, 232 quotes)

Topic: curried functions (14 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 side effects (11 items)
Topic: higher-order functions and combinators (19 items)
Topic: incremental development (74 items)
Topic: initialized constants (12 items)
Topic: lambda calculus (16 items)
Topic: no need for replacement (4 items)
Topic: orthogonal extension and cartesian products (11 items)
Topic: procedures as data (22 items)
Topic: programming as mathematics (27 items)
Topic: programming with a database of modules (94 items)
Topic: reduction languages (17 items)
Topic: referential transparency (26 items)
Topic: sequence reduction (10 items)
Topic: type algebras, typed lambda calculus, and type-complete languages (28 items)
Topic: universal data type (18 items)
Topic: problems with the von Neumann architecture
(11 items)

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