Lambda Calculus as an alternative to Logic based systems
In this text I'll try to interest readers in alternative way of dealing with knowledge bases which would naturally involve logic programming.
The first thing that comes to my mind on mention of AI is Logic. Logic, having boolean operators and, or, not, together with implication (i-then, if-and-only-if) is something that is wired up inside every natural language people are using all over the world, so at the first sight it seems as a natural place to start when building AI. All forms of conclusions universally written as a kind of formulas build up pretty powerful system that can derive all the knowledge implicitly contained in provided facts. There are many kinds of logic, from propositional and first order to higher order logic, where each successor brings greater expressiveness. There are even multi-valued logics that operate not only on true-false pair, but on entire range between true being 1.0 and false being 0.0, where 1.0 describes 100% probability, and 0.0 describes 0% probability that a certain judgement is true. Probably the simplest logic that operates on ranges of values is Fuzzy Logic, but there are at leas two more complicated, but also more powerful logic systems based on probability ranges of values.
Although logic seems powerful framework for making conclusions, it seems to me that it gets pretty awkward when it comes to describing algorithms (if anyone has experience with Prolog programming language, I'd appreciate to read some critics). Different algorithms are known to be very well described in imperative (state operating) languages, but imperative code look like everything but clean and smart way to store dynamic transformations for a purpose of AI. There are a lot of dirty tricks involved in imperative programming, especially when dealing with memory pointers, which makes algorithm analysis and synthesis more difficult.
Algorithm description, forming a natural description of different processes, have to be a part of an AI system if we want it to be complete, but combination of Logic and imperative programming paradigm looks like everything, but a clever way to describe thing around us. Well, that is where
Lambda Calculus hops in. Lambda calculus is somewhere between logic system and imperative programming paradigm, regarding to its scientific use. It has a power to describe algorithms in a neat way, while retaining a simplicity of rules that drive the system on. Lambda Calculus is not a new thing, it exists from 1930s as a part of foundation of mathematics. Entire programming paradigm called
functional programming is based on Lambda Calculus. It looks a bit odd to switch thinking from imperative to functional way, but once it clicks in our understanding, it is beginning to appear as the most natural system to describe thing around us. There are a lot of fans of functional programming, but it still gets a kind of reserved for dedicated academic circles. To show the power of functional programming, a lot of introductionary books outputs a Quicksort algorithm that in some functional language looks like this:
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y <= x] ++ [x] ++ quicksort [y | y <- xs, y > x]
Compare it to Python (imperative language) implementation
def quicksort(x):
if len(x) == 1 or len(x) == 0:
return x
else:
pivot = x[0]
i = 0
for j in range(len(x)-1):
if x[j+1] < pivot:
x[j+1],x[i+1] = x[i+1], x[j+1]
i += 1
x[0],x[i] = x[i],x[0]
first_part = quicksort(x[:i])
second_part = quicksort(x[i+1:])
first_part.append(x[i])
return first_part + second_part
It is obvious that a kind of mystic power lays behind functional programming languages based on Lambda Calculus. The best of all, functions on which is based Lambda calculus are equivalent to mathematical definition of functions, which brings a power of mathematical solutions right under your fingers. Moreover, as everything can be described as a kind of function, thus logical conclusions can be described as functions that take premises as function parameters, and return conclusions as a function result. In short, with Lambda calculus we deal with a part of math in which it is possible to describe the almighty logic framework, while keeping common sense properties needed for describing arbitrary algorithms. Of course, like entire logic, entire math also can be described in lambda calculus, which could make it an attractive choice for programming AI.
Alonzo Church, the guy who invented Lambda Calculus, made an additional effort needed to test his work, and provided us with
Church encoding. Church encoding spans from logical symbols and operators to mathematical symbols and operators, thus rounding a whole that could be chosen instead of logic alone when building AI system.
I hope you didn't find this exposure boring. We touched one of the alternatives to pure logic system when it comes to programming AI, how ever "programming AI" might seem abstract. I believe that functional programming is a great invention and that it deserves at least to be known that it exist as an alternative to both commercial programming and AI logic programming.
