Hierarchy
of formal languages
FunLog++ is a declarative programming
language with elements from functional
as well as from logic programming.
formal language imperative - state modification - essentially sequential declarative pure functional - functional notation - directed input/output - strongly typed - call by value - evaluation by reduction (term rewriting) pure logic - relational notation - undirected input/output - often untyped - call by unification - evaluation by resolution functional+logic
functional programming:We call FunLog++ to be functional as evaluation of terms only communicated via parameter positions (in contrast to side effects in imperative languages, e.g. PASCAL) and as terms return a value (in contrast to relational notation as in some logic languages, e.g. PROLOG).
logic programming: We call FunLog++ to be a logic programming language as it uses logical variables and it provides implication and unification as its basic operations.
logical variable: First-class object which can occur in values of other variables. The value of a (logical) variable can be built incrementally by beginning with a skeleton and binding contained variables later as information becomes available(Smolka 1986)
first class object: Data structure that may be input to predicates and obtained as output bindings (Reddy 1986).
unification: To unify two objects is to try to make them equal by mutual binding variables and (sub-)terms. Unification is defined to produce the most general common instance. Unification plays the role of pattern matching, evaluation, message passing, inheritance, and symbolic evaluation.
syntactic unification:We call unification A=B to be syntactic if parameters A and B are matched without further evaluation.
semantic unification: Unification is called semantic if parameter A and B are first evaluated and then the results are syntactically unified.
extensible unification: We call unification to be extensible if the matching algorithm may be redefined for new datatypes or new object classes.
(pattern) matching: Special kind of unification where one parameter (the pattern) contains no variable.
eager evaluation: With eager evaluation terms are evaluated completely before the context (search depth-first).
lazy evaluation: With lazy evaluation terms (messages) are evaluated as late as possible and only if required (search breadth-first).
extensional properties: Properties of the functions computed by the program. Examples of extensional properties are notions of equality for streams and co-routines, characterizing streams by sequences they generate, characterizing operations on co-routines as operations on infinite sequences, and characterizing programs implementing search strategies as functions parameterized by functions describing the search space (Talcott 1986).
intensional properties: Properties of the computations described by the program. Examples of intensional properties are the number of inference steps executed, the number of context switches, the maximum stack depth required in a computation, and the trace of a computation. Intensional properties can be used to design programs that are efficient or that can be made efficient by systematic transformations (Talcott 1986).
Francis G. McCabe: Logic and Objects. Series in Computer Science, Prentice Hall International, NewYork 1992, ISBN 0-13-536079-X
Richard Bird and Philip Wadler: Introduction to Functional Programming. Series in Computer Science, Prentice Hall International, NewYork 1988, ISBN 0-13-484189-1
Rinus Plasmeijer, Marko van Eekelen: Functional Programming and Parallel Graph Rewriting. NewYork, Addison Wesley, 1993
Uday S. Reddy: On The Relationship between Logic and Functional Languages, in: DeGroot 1986, pp. 3-36
Gerd Smolka: FRESH: A Higher-Order Language with Unification and Multiple Results, in: DeGroot 1986, pp. 469-524
Doug DeGroot and Gary Lindstorm: Logic Programming - Functions, Relations and Equations, 1986, London, Prentice Hall, ISBN 0-13-539958-0,
Carolyn Talcott: Rum - An intensional theory of function and control abstractions, in: Boscarol 1986, pp. 3-44
M.Boscarol,
L.Carlucci Aiello, and G. Levi: Foundations of Logic and Functional Programming,
Workshop Trento, Italy, December 1986, Proceedings edited by , Lecture
notes in computes science, no. 306 (Springer, Berlin), ISBN 0-387-19129-1
|
|
|
|
==> FunLog++ www entry - introduction - glossary - reference - library - tutorial - demo <==