Lambda Calculus – The Math Behind Functional Programming

Functional Programming (FP) Languages : Lisp, Haskell, Scala, Kotlin, etc.

Other non-FP influenced by Lambda Calculus: Python, Ruby, Javascript, Java 8, C++

Inventor of Lambda Calculus : Alonzo Church (1903 – 1995), whose student in Princeton University (1936-1938) was Alan Turing (The Father of Artificial Intelligence).

Lambda Calculus is not : another Differential Calculus !

Note: Calculus has a meaning of manipulating symbolic expressions : either in functions (differentiation, integration) or computations.

Lambda Calculus is almost programming!

I. Syntax of Lambda Calculus: \boxed {\lambda \text { param . body }}

eg. \lambda \: x \: . \: x + 1

Notice: it has only one parameter “x”.

  1. Function definition: \lambda
  2. Identifier reference: x
  3. Function application: x + 1

II. Currying 柯里化 : (named after Haskell Curry ) for multiple parameters.

eg. \lambda \: x \: . \: (\lambda \: y \: . \: x + y)

written by “Currying” as : \boxed { \lambda \: x \: y \: . \: x + y}

Syntactic Sugar 语法糖 : a notational shorthand. Eg. “cubic”
cubic = λ x . x * x * x

III. Binding: Every parameter (aka variable) must be declared (syntactically binding).

eg. \lambda \: x \: . \: z x

here, x is bound, but z is FREE (error!)

IV. Two Execution Methods:

1. \alpha \text{ conversion }

  • rename variables to avoid conflict

2. \beta \text{ reduction} \text { - Apply a function}

  • Eager evaluation strategy : Right to Left (innermost expression first to outermost) or
  • Lazy evaluation strategy : Left to Right (outermost expression first to innermost) – don’t compute the value of an expression until you need to – (save memory space and computing time)
  • Most FP are Lazy.
  • Most Procedural (Imperative) languages (C, Fortran, Basic, …) are Eager.

V. Lambda Calculus fulfilling the 3 conditions for “Turing Complete” Computation :

  • UnboundedStorage” (not necessarily a physical device) – generate arbitrarily complicated values in a variable or many functions without bound.
  • Arithmetic – Church numerals (Peano arithmetic using functions): eg z=0, s= z+ 1 => 1 = λ s z . s z => 2 = λ s z . s ( s z ) … => 7= λ s z . s (s(s(s(s(s(s(z )))))))
  • Control Flow – TRUE = λ t f . t / FALSE = λ t f . f / BoolAnd = λ x y . x y FALSE / BoolOr = λ x y . x TRUE y / Repetition by Recursion (Y Combinator )

Conclusion: Lambda Calculus = “Computer on paper”

VI. Type – Consistent Model (notation “:“)

eg. λ x : I . x + 3 ( I is Integer Type)

=> The result (x + 3) is also Type I since by inference “+” is of Type I -> I

Reference: “Good Math” by Mark Chu-Carroll https://www.amazon.com/Good-Math-Computation-Pragmatic-Programmers/dp/1937785335/

Advertisements

Category Theory – Purest of pure mathematical disciplines may also be a cornerstone of applied solutions in computational science

There exists in almost all Universities a clear division between pure and applied mathematics. A friendly (and sometimes not so friendly) rivalry exists between both sides of the divide, with separate conferences, separate journals and in many cases even a whole separate language. Category Theory was seen as such an abstract area of research that even pure mathematicians started to refer to it as “abstract nonsense“, and until the mid 1980’s almost all category theorists occupied a place hidden somewhere up above the ‘cloud level’ in the highest reaches of the peaks that defined “pure” maths.

By the mid 1990’s and then by the turn of the millenium, a whole world of computer programmers were learning basic category theory as part of their induction into functional programming. The best known product of these efforts is the Haskell language, but even in the past 7 or 8 yrs, workshops on category theory for computer programmers of all types have flourished and proliferated. It is almost as if there are two separate communities masquerading as one – mathematical category theory and computer programming category theory – and never the twain would meet. Or so it seemed, until now.

https://www.linkedin.com/pulse/category-theory-classic-dichotomy-purest-pure-may-also-khan-ksg/

A Fistful of Monads

Kotlin Monad (and Functor, Applicative)

1. Functor “map” (Kotlin) (fmap or <$> in Haskell)

https://hackernoon.com/kotlin-functors-applicatives-and-monads-in-pictures-part-3-3-832d58d92445

2. Monadsflatmap” (>>= in Haskell)

Haskell Monad:

http://learnyouahaskell.com/a-fistful-of-monads

Do not fear Monoid / Monoidal Category / Monad:

Monad in Haskell

F# Monad:

View story at Medium.com

(分享自知乎网)

https://zhuanlan.zhihu.com/p/29542641

Alternate Admission Route to NUS Computing

Singapore Maths Tuition

Source: http://www.straitstimes.com/singapore/education/nus-eyes-more-aptitude-based-admissions

Good news to students who are interested to study Computer Science. There is now an alternative route for students who are short of the cut-off point (currently at least two A’s).

To win a place on the increasingly popular computer science degree course at the National University of Singapore (NUS), students need at least two As for their A levels. Next year though, students eyeing a computing degree can be admitted through another route.

They can take up a five-month-long computer programming course at NUS and if they do well, gain fast-track admission into the degree course, even though they may fall short of the required grades.

View original post