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

Explore Kotlin’s Advanced Functional Programming

Since May 2017 Kotlin released by Google, 12.8% Java developers have converted to Kotlin, yet they still keep to the OO spirit of Java (for Interoperability) , not taking full advantage of FP capability of Kotlin. The OO Design Patterns of Android Java still being used instead of the FP more elegant “Monadic” Design.

1. Interview with Kotlin Designer:

https://www.mappingthejourney.com/single-post/2017/10/26/episode-12-interview-with-andrey-breslav-lead-language-designer-of-kotlin/

2. Android Studio 3.0 Released : https://www.androidauthority.com/android-studio-3-released-810099/

2a. Android Studio v3.0 with Kotlin built-in & many improvements.

(The previous stable v2.3 needs seperate Kotlin plug-in)

https://thenextweb.com/dd/2017/10/27/android-studio-3-0-brings-support-for-kotlin-java-8-and-instant-Features

2c: Gradle upgrade

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

3. Inner / Infix Function

http://thetechnocafe.com/more-about-functions-in-kotlin/

4. Test (Mockito)

https://proandroiddev.com/improve-your-tests-with-kotlin-in-android-pt-1-6d0b04017e80

https://proandroiddev.com/improve-your-tests-with-kotlin-in-android-pt-2-f3594e5e7bfd

Kluent library:

https://proandroiddev.com/improve-your-tests-with-kotlin-in-android-pt-3-104e1c9f77cc

5. Function vs Procedure vs MethodKotlin simplifies all 3 into 1 : Function which always returns a value or UNIT.

View story at Medium.com

6. Kotlin has which Java lacks … “with“, “?”, …

https://blog.simon-wirtz.de/kotlin-features-miss-java/

7. Kotlin Operator Overloading aka “Convention”: ‘plus’ / ‘+’

https://blog.simon-wirtz.de/kotlin-conventions-operator-overloading/

8. JVM Byte Code Generation:

https://blog.simon-wirtz.de/kotlin-on-the-jvm-byte-code-generation/

9. Reified Types

https://blog.simon-wirtz.de/kotlin-reified-types/

10. SICP: Sequence as conventional interfaces: eg. flatmap, map, reduce, fold

https://dzone.com/articles/conventional-interfaces-in-functional-programming

11.Kotlin中extensions的用法

https://zhuanlan.zhihu.com/weiweidaolai/27537731

12. Generic : Kotlin入门(11)江湖绝技之特殊函数

https://zhuanlan.zhihu.com/aqi00/28302792

13. Array <String>: Kotlin入门(4)声明与操作数组

https://zhuanlan.zhihu.com/aqi00/27744799

14. ViewPager (Horizontal Swipe)

https://www.raywenderlich.com/169774/viewpager-tutorial-android-getting-started-kotlin

15. Kotlin 1.2 Beta & Multiplatform iOS

https://blog.jetbrains.com/kotlin/2017/11/kotlinconf-keynote-recap/

16. Kotlin Edu ( Android Studio 3.0)

https://www.jetbrains.com/education/kotlin-edu/

17. Kotlin Style Guide

https://android.github.io/kotlin-guides/style.html

18. Android Layout FoundamentalConstraintLayout

https://developer.android.com/guide/topics/ui/declaring-layout.html

19. Android SDK

https://www.raywenderlich.com/171148/android-sdk-versions-tutorial-2

20. Javalin v1.0 – Web Framework for Java + Kotlin

https://jaxenter.com/javalin-1-0-is-here-138750.html

21. Ten Modern Features (Kotlin, Clojure, Javascript, Swift…)

View story at Medium.com

22. Function literals with receiver

https://blog.simon-wirtz.de/function-literals-with-receiver-quick-introduction/#page

23. Sealed classes: (restricted types no “else”)

https://mindorks.com/course/advance-kotlin/chapter/id/1

24. Android Intent

https://www.raywenderlich.com/171071/android-intents-tutorial-kotlin

25. Top kotlin tutorials

View story at Medium.com

26. Kotlin Contexts & Shared Preferences

https://blog.stylingandroid.com/kotlin-contexts-sharedpreferences/

27. Delegation – but not Inheritance (which takes all)

https://blog.kotlin-academy.com/superpowers-of-kotlin-delegation-e6bd9ff8026c

28. Functions or Properties Reference (cool *)

View story at Medium.com

29. Web Framework ktor:

https://blog.simon-wirtz.de/web-app-kotlin-ktor/