Functional Languages

$\lambda$-calculus vs TM

$\lambda$-calculus	Turing Machine
Not compatible with hardware	Naturally compatible with hardware
Has natural syntax	No natural syntax
Has natural notion of code and organization of code	No natural organization

Functional programming

• von Neumann style is not the terminal model for programming

  "Can programming be liberated from the von Neumann style? A functional style and its algebra of programs", Turing Award Lecture, John Backus, 1977

  John Backus received the Turing Award for the invention of the FORTRAN programming langauge, one of the first successful von Neumann languages.

• Functional programming comes from $\lambda$-calculus

  $\lambda$-calculus is the foundation of all functional programing languages. Its rewrite rules $\alpha$-conversion, $\beta$-conversion and $\eta$-conversion are still part of modern day functional programming compilers.

• Functional programming is durable.

  • Lisp: 1955-1970
  • MacLisp: (MIT's Mathematics and Computation project): 1965-1990
  • Scheme, Racket, 1975 - now
  • Common Lisp: 1980 - now
  • Clojure: 2004 - now

• Functional programming is diverse:

  • OCAML: 1996 - now
  • Haskell: 1990 - now
  • Erlang: 1986 - now

• Functional programming is productive:

  box

  Jane Street

  • "A quantitative trading firm with a unique focus on technology and collaborative problem solving."
  • Trade $21 billion/day in global equities, bond and ETFs.
  • Uses OCAML in production

  box

  Facebook Sigma

  • "... proactively identify malicious actions on Facebook, such as spam, phishing attacks, posting links to malware, etc."
  • Uses Haskell in production

  box

  Walmart

  • "Our Clojure system just handled its first Walmart black Friday and came out without a scratch."
  • Clojure used by eReceipts team at WalmartLabs

  box

  Nubank

  • A financial services startup in Brazil with over 20 million customers
  • Recently acquired Cognitect, the maker of Clojure

• Functional programming is the future:

  Most modern languages supports functional programming.

  • Go from Google
  • Rust from Mozilla
  • Java $\leftarrow$ yes, Java supports lambda functions

$\lambda$-calculus and functional programming

• Functions are building blocks

  Pure $\lambda$-calculus relies on functions to represent data (even integers). Thus, functions are the fundamental building blocks in functional languages.

  von Neumann languages, on the other hand, use functions as an organizational tool to abstract sequences of control logics for the convenience in reasoning and software development.

• Variables are names.

  Recall that names are symbols that can appear in $\lambda$-expressions. They naturally corresponds to variables in programming languages.

  E.g. $$\lambda x. (x+y)$$

• Names have scopes.

  Scopes for a name is natural. A name is introduced in function abstraction by the $\lambda$ declaration. The scope of the name is the body of the function.

  In functional languages, names can be introduced in many ways, and their scopes have more complicated definitions.

• Names are read-only bindings to values.

  Contrary to von Neumann languages, names in $\lambda$-calculus cannot change their values in the scope. They represent the values assigned to them, not references to memory address that store these values.