SITC Holds Seminar on Lambda Calculus & Functional Programming

The Dean of the SITC, Dr. Mathias Fonkam, and Dr. Rajesh Prasad, Assistant Professor in the SITC, were presenters, April 7, of an SITC seminar titled: Lambda Calculus & Functional Design.

In explaining the Lambda Calculus, Dean Fonkam said it was introduced in the early 1930's by researchers at Princeton University as a function theory that could be used to mechanize information processing or computation, albeit on paper at the time (note that this was way before the first digital computer was built). 

The work of the Princeton researchers actually built on the work of a 1920's Russian mathematician, Moses Schonfinkel, titled combinatory logic where he had introduced several base functions (the combinators) and proved that any other function could be expressed in terms of these.  The idea of the lambda calculus is based on function abstraction and function application through a single mechanical process known as beta-substitution - substitution of formal parameters with actual parameters when functions are called or applied.  The complete syntax specification for the lambda calculus is no more than three lines long, so it is remarkable that it represents a complete and general-purpose programming system capable of being used to compute all the computable set of problems as expected of any mainstream programming language such as Ruby, Java, or C. 

Yet, the syntax specification alone for these high-level languages can run into hundreds or thousands of pages.  These early computer scientists (Mathematicians) did not only identify the class of problems that were computable, they also identified some important capabilities that a complete programming system needed to support to be a general purpose programming tool, and proved that the Lambda Calculus indeed met these requirements.  This has come to be known as the Turing completeness test. 

Dean Fonkam noted, "Lambda Calculus represents the world’s smallest programing language.”  All computations can be expressed in it, so much of the "extra baggage" in high level languages like Java or Ruby simply represent what computer scientists call syntax sugar or conveniences.  In the lambda calculus, computations are abstracted as functions that map inputs to outputs.  The computations are completely defined by both the function mappings and their inputs and for the same inputs and mappings, the outputs are always the same.  This yields code that can be more easily verified for correctness.

Another key property of pure functional programming as in the lambda calculus is that programs (or functions) can only change their inputs, hence have no side effects on other programs that may be running in parallel.  Programs do not share state and cannot affect global state.

Dean Fonkam noted that LISP, a functional programming language deriving directly from the Lambda Calculus, was the second major programming language invented by AI researchers at MIT in the late 50's.  He noted that LISP (and its descendant functional programming languages) was perhaps too far ahead of its time then in the late 1950's, as it was little employed for a long time outside of the AI community and by researchers.  He also noted that all high-level programming languages, irrespective of whether they were classified as functional or not, support the capability of defining and applying functions to some extent.  He went on to show the relevance of functional programming in our age of technological advancements and exponential growth in data and processing needs.  He said we have hit the limit of Moore's Law (that said CPU speed was doubling every two years or so) and the only way now to increase processing speed is by chaining multiple processors horizontally and dividing work amongst them.  Unfortunately, most traditional imperative (non-pure functional) programming languages were created to support vertical scaling through difficult programming mechanisms such as multi-threading or multiprocessing.

Dean Fonkam explained how the functional programming style comes to the rescue in facilitating horizontal scaling where we can simply chain cheap commodity computers and have them store and process in parallel, but safe in the knowledge they will not corrupt any shared data or each other's work.  He said, “We treat each machine as a function…Because in functional programming, there is no shared data; every function has its data or input.  If you use the same input, you get the same output.”

Dean Fonkam explained that Cloud Computing is becoming the standard way of doing computing by all these days -- described by many as the fifth utility where you simply subscribe to a Cloud Service and pay for just what you use.  It is backed by data centers operated by software giants like Amazon, Google, Microsoft, Apple etc. and at the heart of the processing of their huge volumes of data and load sharing by thousands or millions of processors is functional programming or some great ideas emanating from this way of programming.  Functional programming enables higher levels of abstraction far removed from the mundane details of the computer (0's and 1's or bits).

In his segment of the seminar, Dr. Prasad demonstrated several example programs written in the DrRacket functional programming environment.  He noted that certain programs would be very hard to implement in the common (non-functional) high level programming languages like Java.  He also added that functional program is closer to the way we think.  “The more we can program in a problem-domain language, the better for us.”

He added that that all AUN students are now being introduced to computer problem solving using the DrRacket FP environment in the required GenEd course: CIE 111 - Introduction to Computers & Computing.  Computational thinking is a key skill for all these days!

By Omorogbe Omorogiuwa  

American University of Nigeria
98 Lamido Zubairu Way
Yola Township bypass
PMB 2250, Yola
Adamawa State, Nigeria

Tel: +234 805 200 2962



Privacy Policy


Copyright © 2018 American University of Nigeria. All Rights Reserved.