ফাংশনভিত্তিক প্রোগ্রামিং

ফাংশনভিত্তিক প্রোগ্রামিং (ইংরেজি: Functional programming) কম্পিউটার প্রোগ্রামিং-এর একটি ঘরানা যেখানে গণনাকে গাণিতিক ফাংশনের মূল্যায়ন হিসেবে গণ্য করা হয়, এবং যেখানে অবস্থা ও পরিবর্তনশীল উপাত্ত এড়িয়ে চলা হয়। নির্দেশমূলক প্রোগ্রামিং-এর মত অবস্থার পরিবর্তন নয়, বরং ফাংশনের ব্যবহারের ওপর এখানে জোর দেয়া হয়। [১]

ফাংশনভিত্তিক প্রোগ্রামিং-এর গুরুত্বপূর্ণ ধারণাগুলির মধ্যে আছে উচ্চ-ক্রম এবং প্রথম-শ্রেণীর ফাংশনসমূহ, সমাপ্তি, এবং পুনরাবৃত্তি। ফাংশনভিত্তিক প্রোগ্রামিং ভাষাগুলির অন্যান্য সাধারণ বৈশিষ্ট্যের মধ্যে রয়েছে ধারাবাহিকতা, হিন্ডলি-মিলনার টাইপ অবরোহী ব্যবস্থাসমূহ, অ-কঠোর মূল্যায়ন (যার মধ্যে "অলসতা" অন্তর্গত), এবং মনাডসমূহ

ফাংশনভিত্তিক ভাষাসমূহের মধ্যে এপিএল, এরলাং, হ্যাস্কেল, লিস্প, এমএল, এবং স্কিম উল্লেখযোগ্য।

Functional programming languages, especially "purely functional" ones, have largely been emphasized in academia rather than in commercial software development. However, notable functional programming languages used in industry and commercial applications include Erlang (concurrent applications),[২], R (statistics)[৩], Mathematica (symbolic math),[৪] Haskell,[৫][৬] ML,[৭] J and K (financial analysis), and domain-specific programming languages like XSLT.[৮][৯]

The lambda calculus forms the foundation for most models of functional programming.

Historyসম্পাদনা

Lambda calculus provides a theoretical framework for describing functions and their evaluation. Though it is a mathematical abstraction rather than a programming language, it forms the basis of almost all functional programming languages today.

Combinatory logic is an equivalent theoretical foundation, developed by Moses Schönfinkel and Haskell Curry. It was originally developed to achieve a clearer approach to the foundations of mathematics.[১০] Combinatory logic is commonly perceived as more abstract than lambda calculus and preceded it in invention.

An early functional-flavored language was LISP, developed by John McCarthy while at MIT for the IBM 700/7000 series scientific computers in the late 1950s.[১১] LISP introduced many features now found in functional languages, though LISP is technically a multi-paradigm language. Scheme and Dylan were later attempts to simplify and improve LISP.

Information Processing Language (IPL) is sometimes cited as the first computer-based functional programming language. It is an assembly-style language for manipulating lists of symbols. It does have a notion of "generator", which amounts to a function accepting a function as an argument, and, since it is an assembly-level language, code can be used as data, so IPL can be regarded as having higher-order functions. However, it relies heavily on mutating list structure and similar imperative features. So, while IPL is certainly a precursor to functional programming, it cannot be regarded as functional itself, even to the extent that Lisp is functional.[তথ্যসূত্র প্রয়োজন]

Kenneth E. Iverson developed the APL programming language in the early 1960s, described in his 1962 book "A Programming Language." APL was the primary influence on John Backus's FP programming language. In the early 1990s, Iverson and Roger Hui created a successor to APL, the J programming language. In the mid 1990s, Arthur Whitney, who had previously worked with Iverson, created the K programming language, which is used commercially in financial industries.

John Backus presented the FP programming language in his 1977 Turing Award lecture Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. He defines functional programs as being built up in a hierarchical way by means of "combining forms" that allow an "algebra of programs"; in modern language, this means that functional programs follow the principle of compositionality. Backus's paper popularized research into functional programming, though it emphasized function-level programming rather than the lambda-calculus style which has come to be associated with functional programming.

In the 1970s the ML programming language was created by Robin Milner at the University of Edinburgh, and David Turner developed the language Miranda at the University of Kent. ML eventually developed into several dialects, the most common of which are now Objective Caml and Standard ML. The Haskell programming language was released in the late 1980s in an attempt to gather together many ideas in functional programming research.

Conceptsসম্পাদনা

A number of concepts and paradigms are specific to functional programming, and generally foreign to imperative programming (including object oriented programming). However, programming languages are often hybrids of several programming paradigms so programmers using "mostly imperative" languages may have utilized some of these concepts.[১২]

Higher-order functionsসম্পাদনা

Functions are higher-order when they can take other functions as arguments, and return them as results. (The derivative and antiderivative in calculus are examples of this).

Higher-order functions are closely related to first-class functions, in that higher-order functions and first-class functions both allow functions as arguments and results of other functions. The distinction between the two is subtle: "higher-order" describes a mathematical concept of functions that operate on other functions, while "first-class" is a computer science term that describes programming language entities that have no restriction on their use (thus first-class functions can appear anywhere in the program that other first-class entities like numbers can, including as arguments to other functions and as their return values).

Higher-order functions enable currying, a technique in which a function is applied to its arguments one at a time, with each application returning a new (higher-order) function that accepts the next argument.

Pure functionsসম্পাদনা

Purely functional programs have no side effects. This makes it easier to reason about their behavior. For example, the result of applying a pure function to pure arguments does not depend on the order of evaluation. As a result, a language which has no impure functions (a "purely functional language," such as Haskell) may use call-by-need evaluation. However, not all functional languages are pure. The Lisp family of languages are not pure because they allow side-effects.

Since pure functions do not modify shared variables, pure functions can be executed in parallel without interfering with one another. Pure functions are therefore thread-safe, which allow interpreters and compilers to use call-by-future evaluation.

Pure functional programming languages typically enforce referential transparency, which is the notion that 'equals can be substituted for equals': if two expressions have "equal" values (for some notion of equality), then one can be substituted for the other in any larger expression without affecting the result of the computation. For example, in

y = f(x) * f(x); 	

a compiler can factor out f(x) if it is pure, transforming the program to

z = f(x); 	 
y = z * z; 	

and eliminating the second evaluation of the (possibly costly) call to f(x). This optimization is called common subexpression elimination.

However, if a function has side effects, the function call cannot be eliminated. Consider the following program fragment:

y = random() * random(); 	

The second call to random cannot be eliminated, because its return value may be different from that of the first call. Similarly,

y = printf("x") * printf("x"); 	

cannot be optimized away; even if printf returns the same value both times, failing to make the second call would result in different program output.

Most compilers for imperative programming languages do not perform common subexpression elimination for function calls, because they do not track whether a function is pure. It is possible for an advanced compiler to infer whether a local function has effects and optimize accordingly; however, most pre-compiled libraries do not expose this information, preventing calls to external functions from being optimized away. Some compilers, such as gcc, add extra keywords for a programmer to explicitly mark pure functions so that this optimization can be performed.

Recursionসম্পাদনা

Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, allowing an operation to be performed over and over. Recursion may require maintaining a stack, but tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. The Scheme programming language standard requires implementations to recognize and optimize tail recursion.

Common patterns of recursion can be factored out using higher order functions, catamorphisms and anamorphisms (or "folds" and "unfolds") being the most obvious examples. Such higher order functions play a role analogous to built-in control structures such as loops in imperative languages.

Strict, Non-strict and Lazy Evaluationসম্পাদনা

Functional languages can be categorized by whether they use strict or non-strict evaluation, concepts that refer to how function arguments are processed when an expression is being evaluated. To illustrate, consider the following two functions f and g:

f:=x^2+x+1
g:=x+y

The following expression can be evaluated in one of two ways.

f(g(1, 4))

Evaluate the innermost function g first:

f(g(1, 4))   →   f(1+4)   →   f(5)   →   5^2+5+1   →   31

Or evaluate the outermost function f first:

f(g(1, 4))   →   g(1,4)^2+g(1,4)+1   →   (1+4)^2+(1+4)+1   →   5^2+5+1   →   31

The first case is an instance of strict evaluation: arguments to a function are evaluated before the function call; while the second case is an instance of non-strict evaluation where arguments are passed to the function unevaluated and the calling function determines when the arguments are to be evaluated.

Strict evaluation has efficiency advantages. An argument is evaluated once with strict evaluation, while it may be evaluated multiple times with non-strict evaluation, as can be seen in the above example where g(1,4) is evaluated twice. Also, strict evaluation is easier to implement since the arguments passed to a function are data values, whereas with non-strict evaluation arguments may be expressions, requiring some notion of closure. As a consequence the earliest functional languages, such as Lisp, ISWIM and ML, along with many of the modern functional languages use strict evaluation.

However there are reasons for preferring non-strict evaluation. Lambda calculus provides a stronger theoretic foundation for languages that employ non-strict evaluation. Also non-strict evaluation provides for a more expressive language. For example it supports infinite data structures such as a list of all positive integers or all prime numbers. With non-strict evaluation these structures are only evaluated in contexts where a finite subset of the list is required. This led to the development of lazy evaluation, a type of non-strict evaluation where the results of an initial evaluation of any argument can be shared throughout the evaluation sequence. As a result an argument is never evaluated more than once. Lazy evaluation is used by the more modern, pure functional languages such as Miranda, Clean and Haskell.

Functional programming in non-functional languagesসম্পাদনা

It is possible to employ a functional style of programming in languages that are not traditionally considered functional languages.[১৩] Some non-functional languages have borrowed features such as higher-order functions, and list comprehensions from functional programming languages. This makes it easier to adopt a functional style when using these languages. Functional constructs such as higher-order functions and lazy lists can be obtained in C++ via libraries.[১৪] In C one can use function pointers to get some of the effects of higher-order functions, for example one can implement the common function map using function pointers. Widespread declarative domain specific languages like SQL and Lex/Yacc, while not Turing-complete, use some elements of functional programming, especially in eschewing mutable values.[১৫]

Comparison of functional and imperative programmingসম্পাদনা

Functional programming is very different from imperative programming. The most significant differences stem from the fact that functional programming avoids side effects, which are used in imperative programming to implement state and I/O. Pure functional programming disallows side effects completely. Disallowing side effects provides for referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks.

Higher order functions are rarely used in older imperative programming. Where a traditional imperative program might use a loop to traverse a list, a functional style would often use a higher-order function, map, that takes as arguments a function and a list, applies the function to each element of the list, and returns a list of the results.

Simulating stateসম্পাদনা

There are tasks—for example, maintaining a bank account balance—that often seem most naturally implemented with state. Pure functional programming performs these tasks, and I/O tasks such as accepting user input and printing to the screen, in a different way.

The pure functional programming language Haskell implements them using monads, derived from category theory. Monads are extremely powerful and offer an intuitive way to model state (and other side effects such as IO) in an imperative manner without losing purity. While existing monads are easy to use, many find it difficult to understand how to define new monads (which is sometimes needed for certain types of libraries).[১৬] Alternative methods such as Hoare logic have been developed to track side effects in programs. Some modern research languages use effect systems to make explicit the presence of side effects.

Efficiency issuesসম্পাদনা

Functional programming languages have automatic memory management with garbage collection, in contrast to older imperative languages like C and Pascal which use explicit memory management. Functional programming languages have been perceived as less efficient in their use of CPU and memory than those languages. However, many modern imperative languages such as Java, Perl, Python, and Ruby also perform automatic memory management.

Functional programming languages have become more efficient over the years. For programs which perform intensive numerical computations, functional languages such as OCaml and Clean are similar in speed to C. For programs that handle large matrices and multidimensional databases, array functional languages (such as J and K) were designed with speed optimization in mind. Despite purely functional languages having a reputation for being slower, any imperative algorithm is expressible in these languages with a logarithmic slowdown in the worst case. Moreover, the immutability of data can in many cases lead to greater execution efficiency owing to the compiler making assumptions that are unsafe in an imperative language.

Coding stylesসম্পাদনা

Imperative programs tend to emphasize the series of steps taken by a program in carrying out an action, while functional programs tend to emphasize the composition and arrangement of functions, often without specifying explicit steps. A simple example of two solutions to the same programming goal (using the same multi-paradigm language Python) illustrates this.

# imperative style
target = []               # create empty list
for item in source_list:  # iterate over each thing in source
    trans1 = G(item)      # transform the item with the G() function
    trans2 = F(trans1)    # second transform with the F() function
    target.append(trans2) # add transformed item to target

A functional version has a different feel to it:

# functional style
def compose2(F, G):       # FP-oriented languages often have standard compose()
    def C(item):          # here we create utility-function for composition
        return F(G(item))
    return C
target = map(compose2(F,G), source_list)

More compact examples of the functional paradigm in Python:

# uses a lambda form in the map function
target =  map(lambda item: F(G(item)), source_list)

or:

# using a list comprehension
target = [F(G(item)) for item in source_list]

In contrast to the imperative style that describes the steps involved in building target, the functional style describes the mathematical relationship between source_list and target.

আরও দেখুনসম্পাদনা

-->

তথ্যসূত্রসম্পাদনা

  1. Hudak, Paul (১৯৮৯)। "Conception, evolution, and application of functional programming languages" (PDF)ACM Computing Surveys21 (3): 359–411। ২০ মার্চ ২০০৯ তারিখে মূল (PDF) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২৮ এপ্রিল ২০০৭  অজানা প্যারামিটার |month= উপেক্ষা করা হয়েছে (সাহায্য)
  2. "Who uses Erlang for product development?"Frequently asked questions about Erlang। সংগ্রহের তারিখ ২০০৬-০৬-২৭  #"The largest user of Erlang is (surprise!) Ericsson. Ericsson uses it to #write software used in telecommunications systems. Many (dozens) projects have #used it, a particularly large one is the extremely scalable AXD301 ATM switch." Other commercial users listed as part of the FAQ include: Nortel, Deutsche Flugsicherung (the German national air traffic control organisation), and T-Mobile.
  3. The useR! 2006 conference schedule includes papers on the commercial use of R
  4. Department of Applied Math, University of Colorado। "Functional vs. Procedural Programming Language"। ২০০৭-১১-১৩ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০০৬-০৮-২৮ 
  5. "Haskell and the Linspire Toolchain"। ১৪ মার্চ ২০০৭ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২৮ এপ্রিল ২০০৭ 
  6. "Why Functional Programming Matters to Credit Suisse"। ১৪ মার্চ ২০০৭ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২৮ এপ্রিল ২০০৭ 
  7. "Caml Trader: Adventures of a Functional Programmer on Wall Street"। ১৪ মার্চ ২০০৭ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২৮ এপ্রিল ২০০৭ 
  8. Dimitre Novatchev। "The Functional Programming Language XSLT - A proof through examples"TopXML। সংগ্রহের তারিখ May 27  অজানা প্যারামিটার |accessyear= উপেক্ষা করা হয়েছে (|access-date= ব্যবহারের পরামর্শ দেয়া হচ্ছে) (সাহায্য); এখানে তারিখের মান পরীক্ষা করুন: |সংগ্রহের-তারিখ= (সাহায্য)
  9. David Mertz। "XML Programming Paradigms (part four): Functional Programming approached to XML processing"IBM developerWorks। সংগ্রহের তারিখ May 27  অজানা প্যারামিটার |accessyear= উপেক্ষা করা হয়েছে (|access-date= ব্যবহারের পরামর্শ দেয়া হচ্ছে) (সাহায্য); এখানে তারিখের মান পরীক্ষা করুন: |সংগ্রহের-তারিখ= (সাহায্য)
  10. Curry, Haskell Brooks (১৯৫৮)। Combinatory Logic. Volume I। Amsterdam: North-Holland Publishing Company।  অজানা প্যারামিটার |coauthors= উপেক্ষা করা হয়েছে (|author= ব্যবহারের পরামর্শ দেয়া হচ্ছে) (সাহায্য)
  11. McCarthy, John (১৯৭৮)। "History of Lisp"In ACM SIGPLAN History of Programming Languages Conference: 173—196।  অজানা প্যারামিটার |month= উপেক্ষা করা হয়েছে (সাহায্য) " The implementation of LISP began in Fall 1958."
  12. Dick Pountain। "Functional Programming Comes of Age"BYTE.com (August 1994)। ২৭ আগস্ট ২০০৬ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ August 31  অজানা প্যারামিটার |accessyear= উপেক্ষা করা হয়েছে (|access-date= ব্যবহারের পরামর্শ দেয়া হচ্ছে) (সাহায্য); এখানে তারিখের মান পরীক্ষা করুন: |সংগ্রহের-তারিখ= (সাহায্য)
  13. Hartel, Pieter (২০০৪)। "The Functional C experience" (PDF)The Journal of Functional Programming14 (2): 129–135। ১৯ জুলাই ২০১১ তারিখে মূল (PDF) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২৮ এপ্রিল ২০০৭  অজানা প্যারামিটার |month= উপেক্ষা করা হয়েছে (সাহায্য); অজানা প্যারামিটার |coauthors= উপেক্ষা করা হয়েছে (|author= ব্যবহারের পরামর্শ দেয়া হচ্ছে) (সাহায্য); David Mertz। "Functional programming in Python, Part 3"IBM developerWorks। সংগ্রহের তারিখ ২০০৬-০৯-১৭ (Part 1, Part 2)
  14. McNamara, B.। "FC++: Functional Programming in C++"। ২০০৬-০৬-১৪ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০০৬-০৫-২৮ 
  15. Donald D. Chamberlin and Raymond F. Boyce (১৯৭৪)। "SEQUEL: A structured English query language"। Proceedings of the 1974 ACM SIGFIDET: 249–264। . In this paper, one of the first formal presentations of the concepts of SQL (and before the name was later abbreviated), Chamberlin and Boyce emphasize that SQL was developed "Without resorting to the concepts of bound variables and quantifiers".
  16. Newbern, J.। "All About Monads: A comprehensive guide to the theory and practice of monadic programming in Haskell"। সংগ্রহের তারিখ ২০০৬-০৫-২৭ , "The sheer number of different monad tutorials on the internet is a good indication of the difficulty many people have understanding the concept. This is due to the abstract nature of monads and to the fact that they are used in several different capacities, which can confuse the picture of exactly what a monad is and what it is good for."

নির্বাচিত গ্রন্থপঞ্জিসম্পাদনা

  • Cousineau, Guy and Michel Mauny. The Functional Approach to Programming. Cambridge, UK: Cambridge University Press, 1998.
  • Felleisen, Matthias, Robert Findler, Matthew Flatt, and Shriram Krishnamurthi. How to Design Programs HTDP. MIT Press. 2001. on-line
  • Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
  • Curry, Haskell Brooks and Feys, Robert and Craig, William. Combinatory Logic. Volume I. North-Holland Publishing Company, Amsterdam, 1958.
  • Curry, Haskell Brooks and Hindley, J. Roger and Seldin, Jonathan P. Combinatory Logic. Volume II. North-Holland Publishing Company, Amsterdam * London, 1972.
  • MacLennan, Bruce J. Functional Programming: Practice and Theory. Addison-Wesley, 1990.
  • Pratt, Terrence, W. and Marvin V. Zelkowitz. Programming Languages: Design and Implementation. 3rd ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
  • Salus, Peter H. Functional and Logic Programming Languages. Vol. 4 of Handbook of Programming Languages. Indianapolis, Indiana: Macmillan Technical Publishing, 1998.
  • Thompson, Simon. Haskell: The Craft of Functional Programming. Harlow, England: Addison-Wesley Longman Limited, 1996.

বহিঃসংযোগসম্পাদনা