Lambda Calculus as an alternative to Logic based systems

  • 3 Replies
  • 379 Views
*

ivan.moony

  • Trusty Member
  • **********
  • Millennium Man
  • *
  • 1026
    • Structured Type System
Lambda Calculus as an alternative to Logic based systems
« on: March 29, 2018, 08:51:04 pm »
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:

Code: [Select]
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

Code: [Select]
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.
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

infurl

  • Trusty Member
  • ********
  • Replicant
  • *
  • 605
  • Humans will disappoint you.
    • Home Page
Re: Lambda Calculus as an alternative to Logic based systems
« Reply #1 on: March 29, 2018, 09:34:09 pm »
Great article Ivan. There is no doubt that functional programming (lambda calculus) affords very elegant solutions to many programming problems. Personally I have decades of experience programming with Common Lisp at a professional level and have on occasion been able to implement applications in one afternoon that would have taken weeks using imperative languages. Common Lisp has been referred to as the "tactical nuclear weapon" of software development because it has been used to solve problems that had hitherto remained unsolved.

For those who don't recognise it, the functional programming example that you provided is in Haskell. Though it's not in my toolkit, I know folks who use Haskell in some very large scale commercial projects to great advantage and would support Ivan in highly recommending that you learn it. Here's a tutorial for anyone who would like to do that.

https://www.tutorialspoint.com/haskell/index.htm

Disclaimer: I haven't worked through this particular tutorial but that website generally has very good content.

*

ivan.moony

  • Trusty Member
  • **********
  • Millennium Man
  • *
  • 1026
    • Structured Type System
Re: Lambda Calculus as an alternative to Logic based systems
« Reply #2 on: March 29, 2018, 10:04:19 pm »
May I also note in favor of Lambda Calculus that in it we can define any logic, being propositional, first order, higher order, modal, fuzzy, or whatever we find suitable.

Lambda Calculus is said to be "Turing complete", which I didn't notice someone ever said for any logic framework (there is again uncertainity for Prolog for which I don't have any experience).
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

ivan.moony

  • Trusty Member
  • **********
  • Millennium Man
  • *
  • 1026
    • Structured Type System
Re: Lambda Calculus as an alternative to Logic based systems
« Reply #3 on: April 02, 2018, 01:50:02 pm »
Logic has a notion of "functions", but as far I have investigated, books usually don't go into details how these functions are defined. Maybe one of the ways these functions could be described is Lambda Calculus. But once we define Lambda Calculus, we can define any logic in it, so is it really necessary to implement a logic at root layer above functions? Why not to have functions themselves at root layer, while defining any logic within them?
« Last Edit: April 02, 2018, 02:18:16 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

 


Users Online

41 Guests, 3 Users
Users active in past 15 minutes:
infurl, ivan.moony, squarebear
[Trusty Member]

Most Online Today: 52. Most Online Ever: 208 (August 27, 2008, 09:36:30 am)

Articles