pLISP © '98 Thomas Mahler

Functions for testing Compiler and VM

 // define some simple functions for demonstration
 // and benchmarking

 // compute the factorial (fac 4) = 1*2*3*4 = 24
 (define fac (lambda (n)   
   (if (= n 0)
      1
      (* n (fac (-1 n))))))

 // version of factorial for use with Y Combinator (Y facY 4)
 (define facY 
 (lambda (f n) 
   (if (= n 0) 1 (* n (f (-1 n)))))) 

 // compute fibonacci numbers:
 (define fib (lambda (n)
   (if (= n 0) 
      1
      (if (= n 1)
         1
         (+ (fib (-1 n)) (fib (- n 2)))))))

 // version of fib using Y combinator
 (define fibY (lambda (f n)
   (if (= n 0) 
      1
      (if (= n 1)
         1
         (+ (f (-1 n)) (f (- n 2))))))) 

 // (tak 18 12 6) is a nice benchmark for diverse lisp systems
 // because it only needs small ints
 // and only shallow recursion depths (max. 18)
 // 
 (define tak 
   (lambda (x y z) 
      (if (>= y x)
         z         
         (tak (tak (-1 x) y z) (tak (-1 y) z x) (tak (-1 z) x y )))))

 // tak for use with Y Kombinator: (Y takY 12 6 3)
 (define takY
   (lambda (f x y z) 
      (if (not (< y x))
         z         
         (f (f (-1 x) y z) (f (-1 y) z x) (f (-1 z) x y )))))


 // (umdr '(0 1 2 3 4 5 6 7 8 9)) reverses the list to (9 8 7 6 5 4 3 2 1 0)   
 // due to its very inefficient algorithm it is a nice benchmark for basic
 // lisp functions like car, cdr cons
 // on my machine (P166MMX,64MB Ram, 300000 allocated nodes) umdr takes 17 sec. in interpreted mode
 // for comparison see results from the literature: (Frank Spade, KI-Rundbrief 38, Gesellschaft fuer Informatik)
 // Symbolics 3670: 61 sec.
 // Interlisp (Siemens 7.5500): 55 sec.
 // Xerox 1108: 165 sec.   
 (define umdr 
   (lambda (lst)
      (if (null lst) nil
         (if (null (cdr lst)) lst
            (cons (car (umdr (cdr lst)))
                 (umdr (cons (car lst)
                          (umdr (cdr (umdr (cdr lst)))))))))))
         
 // reverse a list
 (define rev 
   (lambda (l) 
      (if (atomp l) 
         l 
         (append (rev (cdr l)) (cons (car l) nil)))))

   
 // (nlist n) -> (n n-1 n-2 ... 3 2 1)
 // it is a good indicator for the max. possible recursion depth of the interpreter
 // on my machine it is about 3000      
 (define nlist 
   (lambda (n) 
      (if (= n 1) 
         '(1) 
         (cons n (nlist (-1 n))))))

 // Ackermann function (a 3 3) -> 61
 (define a (lambda (n m) 
   (if (= n 0) 
      (+1 m) 
      (if (= m 0) 
         (a (-1 n) 1) 
         (a (-1 n) (a n (-1 m)))))))

 // Ackermann function (a 3 3) -> 61 for use with Y Combinator: (Y a 3 3) -> 61
 (define aY (lambda (f n m) 
   (if (= n 0) 
      (+1 m) 
      (if (= m 0) 
         (f (-1 n) 1) 
         (f (-1 n) (f n (-1 m)))))))


 // compute Gaussian sum 0...n :
 (define add
   (lambda (n) 
      (if (= n 0) 0
         (+ n (add (-1 n))))))

 (define addY
   (lambda (f n) 
      (if (= n 0) 0
         (+ n (f (-1 n))))))

 (cf 'add)
 (cf 'fac)
 (cf 'a)
 (cf 'facY)