CODEWITHSUNDEEP
lisplambda-calculus
Ivan
Ivan

Reputation: 333

Lisp IF-THEN-ELSE Lambda Calc Implementation

I made this IF-THEN-ELSE Lambda Calculus code 

(defvar IF-THEN-ELSE
    #'(lambda(con)
        #'(lambda(x)
            #'(lambda(y)
                #'(lambda(acc1)
                    #'(lambda (acc2)
                        (funcall (funcall (funcall (funcall con x) y) acc1) acc2))))))
)

(defun IF-THEN-ELSEOP(c x y a1 a2)
    (funcall (funcall (funcall (funcall (funcall IF-THEN-ELSE c) x) y) a1) a2)
)

And this Greater or Equal operator

(defvar GEQ
    #'(lambda(p)
        #'(lambda(q)
              (funcall #'LEQOP q p)))
)

LEQOP is a function for "Less or Equal" and it works OK. So when I call IF-THEN-ELSE like this ("six" and "two" are church numbers)

(if-then-elseop GEQ six two (print "THIS") (print "THAT"))

as output I've got

"THIS" 
"THAT" 
"THIS"

Both functions that I'm passing are being called. How can I avoid it in order to get only as output "THIS"?

This happens with every function I use, and this is a trouble because I want to use IF-THEN-ELSE in a recursive call, so just one function must be called dependign on the IF-THEN-ELSE eval.

Any help would be appreciated

Thanks.

Upvotes: 1

Views: 1808

Answers (1)

Faiz
Faiz

Reputation: 16265

Passing your print statements by wrapping them in lambdas should work, but maybe it's worth an explanation as to why this is necessary.

You're implementing a lambda calculus. By definition, all 'things' in the calculus are higher order functions. Your six and two and any other church numerals you may have defined are also higher order functions.

IF-THEN-ELSE is a lambda abstraction (also a higher-order function because it's 'arguments' are also functions). So this would have been valid:

(if-then-elseop GEQ six two one two)

Where one and two are church numbers. By doing that, you're expressing in lambda calculus what you would in plain lisp as:

(if (>= 6 2) 
  1 
  2)

But I'm guessing what you were aiming for was:

(if (>= 6 2) 
  (print "this")
  (print "that"))

(more later about why messing with print might be a distraction to your exercise)

So the 'real' 1 has a church encoding one, which I'me assuming you've defined. That way, it can be applied to the lambda abstraction IF-THEN-ELSE - In the same way that

(>= 6 2)

evaluates to TRUE in the lisp world, your lambda calculus implementation of the same,

((GEQ six) two)

will evaluate to the lambda encoding of TRUE, which is again, encoded as a higher-order function. 

(defvar TRUE #'(lambda (x) #'(lambda (y) x)))
(defvar FALSE #'(lambda (x) #'(lambda (y) y)))

So the rule to remember is that everything you are passing around and getting back in the lambda calculus are functions:

 0 := λf.λx.x             
 1 := λf.λx.f x
 2 := λf.λx.f (f x)
 3 := λf.λx.f (f (f x))
 ... and so on

Which is why, if you did: 

(if-then-elseop GEQ six two 
   #'(lambda () (print "THIS"))
   #'(lambda () (print "THAT")))

should work. (sort of, read ahead)

(I'd stick to the faithful interpretation of IF-THEN-ELSE though:

(defvar IFTHENELSE 
  #'(lambda (p) 
    #'(lambda (a) 
      #'(lambda (b) (funcall (funcall p a) b)))))

Where p is your condition... )

As a side note, it's worth pointing out that it might not be too helpful to bring in print and other code that 'does stuff' within lambda calculus - the calculus does not define IO, and is restricted to evaluation of lambda expressions. The church encodings are a way of encoding numbers as lambda terms; There's no simple and meaningful way to represent a statement with side-effects such a (print "hello") as a lambda term; #'(lambda () (print "THIS")) works but as an academic exercise it's best to stick to only evaluating things and getting back results.

What about lisp itself? if in lisp is not a function so (if cond then-expr else-expr) works the way you expect (that is, only one of then-expr or else-expr will actually be evaluated) because it is a special form. If you were to define your own, you would need a macro (as @wvxvw rightly suggests). But that's another topic.

Upvotes: 1

Related Questions