Programming Languages/Functional Languages

Functional Programming Languages

The idea of declarative programming is to define rules for the working of the environment and then to let the language figure everything else out. This contrasts with procedural languages where one tells a machine exactly what to do. Functional programming can be one of the ways to achieve a declarative programming style. The classic example is a factorial function. The first step in defining a new function is to handle the trivial cases first. Factorial of 0, then, would be defined as 1. The next step is to define non-trivial cases in a way such that they will eventually resolve to the simple cases. Factorial of n, then, would be defined as n multiplied by the Factorial of one less than n:

fac 0 = 1

fac n = (fac (n-1)) * n

A naive implementation like this uses more memory and processing time than a 'for' loop (it uses O(n) stack space), but this can be fixed with a simple change, using an accumulator parameter to enable the compiler or interpreter to eliminate the function-call cost:

facb 0 acc = acc

facb n acc = facb (n-1) (n*acc)

fac n = facb n 1

Functional programming has great uses. One might use a functional language as a prototype of code --it is in many cases easier to write functional code and prove that it will generate the desired result than with procedural languages-- and then optimize it by using procedural techniques. Functional techniques can be very efficient at traversing binary trees.

• TODO: Just describe how popular functional languages differ from lambda calculus, importantly side-effects (but mention Haskell)
  • Scheme and ML both have built in types, like integers, floats, lists and string
  • Scheme has tail-call optimization
  • Scheme has multiple argument functions instead of currying
  • Scheme uses the functional notation for all constructs, requires the parentheses
  • Scheme has hygenic macros
  • ML is statically typed with inference
  • ML has pattern matching constructs
  • ML has only single argument functions, but simulates multiple arguments both with currying and with tuples
  • ML uses the lambda calculus notation for function calls (i.e, no parentheses needed), but uses keywords for built in constructs (i.e. it does not use the functional notation for if)

Because lambda keeps references to the variables referenced in the outscope, yet these functions can be stored and called when the calling function has long returned, languages that use lambda have garbage collection. Functional programming a subset of declarative programming that focuses on writing “pure functions” The functional programming paradigm was explicitly created to support a pure functional approach to problem solving. Functional programming is a form of declarative programming. In contrast, most mainstream languages, including object-oriented programming (OOP) languages such as C#, Visual Basic, C++, and Java, were designed to primarily support imperative (procedural) programming In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions or declarations instead of statements. In functional code, the output value of a function depends only on the arguments that are passed to the function, so calling a function f twice with the same value for an argument x produces the same result f(x) each time; this is in contrast to procedures depending on a local or global state, which may produce different results at different times when called with the same arguments but a different program state. Eliminating side effects, i.e., changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

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 and preceded it in invention.

• Lexical versus dynamic scope