Is there anything like a functional model?

Question

In Object Oriented Paradigm, I would create an object/conceptual model before I start implementing it using OO language.

Is there anything parallel to object model in functional programming. Is it called functional model? or we create the same conceptual model in both the paradigm before implementing it in one of the language..

Are there articles/books where I can read about functional model in case it exist?

or to put it in different way... even if we are using functional programming language, would we start with object model?

Answer 1

In fact there is. There is a form of specification for functional languages based on Abstract Data Types called algebraic specification. Their behavior is very similar to that of objects in some ways, however the constructs are logical and mathematical, and are immutable like functional constructs.

A particular functional specification language that's used in the Algorithms and Data Structures class in the University of Buenos Aires has generators, observers, and additional operations. A generator is an expression that is both an instance and a possible composition of the data type. For example, for a binary tree (ADT bt), we have null nodes, and binary nodes. So we would have the generators:

-nil
-bin(left:bt, root: a, right:bt)

Where left is an instance of a bt, the root is a generic value, and right is another bt. So, nil is a valid form of a bt, but bin(bin(nil,1,nil),2,nil) is also valid, representing a binary tree with a root node with a value of 2, a left child node with a value of 1, and a null child right node.

So for a function that say, calculates the number of nodes in a tree, you define an observer of the ADT, and you define a set of axioms which map to each generator. So, for example:

numberOfNodes(nil) == 0
numberOfNodes(bin(left,x,right))== 1 + numberOfNodes(left) + numberOfNodes(right)

This has the advantage of using recursive definitions of operations, and has the more, formally interesting property that you can use something called structural induction to PROVE that your specification is correct (yes, you demonstrate that your algorithm will produce the proper result).

This is a fairly academic topic rarely seen outside of academic circles, but it's worth it to get an insight on program design that may change the way you think about algorithms and data structures. The proper bibliography includes:

Bernot, G., Bidoit, M., and Knapik, T. 1995. Observational specifications and the indistinguishability assumption. Theor. Comput. Sci. 139, 1-2 (Mar. 1995), 275-314. DOI= http://dx.doi.org/10.1016/0304-3975(94)00017-D

Guttag, J. V. and Horning, J. J. 1993. Larch: Languages and Tools for Formal Specification. Springer-Verlag New York, Inc. Abstraction and Specification in Software Development, Barbara Liskov y John Guttag, MIT Press, 1986.

Fundamentals of Algebraic Specification 1. Equations and Initial Semantics. H. Ehrig y B. Mahr Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, Germany, 1985.

With corresponding links: http://www.cs.st-andrews.ac.uk/~ifs/Resources/Notes/FormalSpec/AlgebraicSpec.pdf http://nms.lcs.mit.edu/larch/pub/larchBook.ps

It's a heck of an interesting topic.