Programming Languages/Functional Languages

Functional Programming Languages

The idea of functional 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. 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. In simple cases like this, much more memory and processing time would be commited than if the function had been written using a simple 'for' loop, but functional programming has great uses. One might use a functional language as a prototype of code --it is in many cases easier 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.

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