1

I started programming with lisp yesterday so please excuse if I am making some really newbie mistake. I am trying to create a function which calculates the bell numbers using the bell triangle and my recursive triangle function is not working properly. I am also sure if I got my recursive triangle function working that my recursive bell function is somehow also broken.

When I test my triangle function I get the output:

(defun bell(l n)
    (if(< n 1)(list 1))
    (if (= n 1)(last l))
    (bell (triangle (reverse l) (last l) (list-length l)) (- n 1))
)
(defun triangle(pL nL i)
    (if(<= i 0)
        (write "equals zero!")
        (reverse nL)
    )
    (triangle pL (append (list (+ (nth i pL) (nth i nL))) nL) (- i 1))  
)
(write (triangle '(1) '(1) 0))


=>


"equals zero!""equals zero!"
*** - NTH: -1 is not a non-negative integer

For some reason, it is printing my debug code twice even though the function should be meeting my base case on the first call.

Improve this question
2
  • I rolled back the edit to the title because while OP is trying to create a triangle, OP has also identified the real issue here: the function isn't terminating at the expected base case, and that's because of the grouping of the ifs. While a solution to the triangle might help OP, the question really is focused on why, for instance, (defun foo (n) (if (= n 0) 35) 42) will always return 42, even if n is 0. It's because the code ignores the result of the if. Commented Apr 13, 2016 at 19:25
  • @JoshuaTaylor I get your point. The OP is not asking about how to solve the triangle but why he is having that error. Anyway, I thought the post could be more helpful and easily found with a more appropriate title, since the current one does not even represent the error. Commented Apr 13, 2016 at 19:50

3 Answers 3

Reset to default
4

For some reason, it is printing my debug code twice even though the function should be meeting my base case on the first call.

It is printed twice because if is not doing what you think it does. The first if test is true, therefore equals zero! is printed. After that, a recursive call to triangle function is invoked. The test is again true (-1 <= 0), so equals zero! is again printed. Finally, you get an error because nthcdr function is called with -1. I strongly recommend you a good lisp debugger. The one from Lispworks is pretty good.

I honestly don't get the logic of what you were trying to achieve with your code. so I wrote mine:

(defun generate-level (l &optional (result))
  "given a list l that represents a triangle level, it generates the next level"
  (if (null l) result
    (if (null result)
        (generate-level l (list (car (last l))))
      (generate-level (cdr l) (append result 
                                      (list (+ (car l) 
                                               (car (last result)))))))))


(defun bell (levels &optional (l))
  "generate a bell triangle with the number of labels given by the first parameter"
  (unless (zerop levels)
        (let ((to-print (if (null l) (list 1) (generate-level l))))
          (print to-print)
          (bell (1- levels) to-print))))

Things to understand the implementation:

  1. &optional (parameter): this parameter is optional and nil by default.
  2. append concatenates two lists. I'm using it to insert in the back of the list.
  3. let ((to-print x)) creates a new variable binding (local variable) called to-print and initialized to x.
  4. I almost forgot to mention how if works in common lisp: (if (= x 1) y z) means if x is equal to 1 then return y, otherwise z.

Now if you call the function to create a Bell triangle of 7 levels:

CL-USER 9 > (bell 7)

(1) 
(1 2) 
(2 3 5) 
(5 7 10 15) 
(15 20 27 37 52) 
(52 67 87 114 151 203) 
(203 255 322 409 523 674 877) 
NIL

It would be nicer to print it with the appropiate padding, like this:

                    1
                 1     2
              2     3     5
           5     7    10    15
       15    20    27    37    52
    52    67    87   114   151   203
203   255   322   409   523   674   877

but I left that as an exercise to the reader.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

A few minor comments on the code: You seem to have an unnecessary AND in BELL. You should also use UNLESS instead of (WHEN (NOT ...)), and the (IF (NULL L) ...) could be moved inside the LET-binding so you don't need to repeat code. Maybe also use COND instead of nested IFs in GENERATE-LEVEL.
@jkiiski Thanks! I haven't coded in Lisp for some time and I'm rusty.
@FrankS101 Thank you for the in-depth explanation and the solution. I eventually figured out the way the if conditional works. Its one of my first jumps from imperative to functional programming so I was floundering a bit. I just needed the nth bell number instead of the entire triangle and this was the least complicated way to achieve that so I chose this approach.
2

Your ifs don't have any effect. They're evaluated, and produce results, but then you discard them. Just like

(defun abc ()
  'a
  'b
  'c)

would evaluate 'a and 'b to produce the symbols a and b, and then would evaluate 'c to produce the symbol c, which would then be returned. In the case of 

(if(<= i 0)
        (write "equals zero!")  ; then 
        (reverse nL)            ; else
    )

you're comparing whether i is less than or equal to zero, and if it is, you print equals zero, and if it's not, you (non-destructively) reverse nL and discard the result. Then you finish the function by making a call to triangle. It seems like you probably want to return the reversed nL when i is less than or equal to zero. Use cond instead, since you can have multiple body forms, as in:

(cond
  ((<= i 0) (write ...) (reverse nL))
  (t (triangle ...)))

You could also use if with progn to group the forms:

(if (<= i 0) 
  (progn 
    (write ...)
    (reverse nL))
  (triangle ...))

Your other function has the same problem. If you want to return values in those first cases, you need to use a form that actually returns them. For instance:

(if (< n 1)
    (list 1)
    (if (= n 1)
        (last l)
        (bell #| ... |#)))

More idiomatic would be cond, and using list rather than l, which looks a lot like 1:

(cond
  ((< n 1) (list 1))
  ((= n 1) (last list))
  (t (bell #| ... |#)))
Improve this answer

Comments

-1

Thank you all for the explanations. I eventually arrived at the code below. I realized that the if block worked something like..

(if (condition) (execute statement) (else execute this statement))

(defun bell(l n)
    (if (< n 2)(last l)
        (bell (triangle l (last l) 0) (- n 1))
    )
)
(defun triangle(pL nL i)
    (if(= i (list-length pL)) nL
        (triangle pL (append  nL (list (+ (nth  i pL) (nth i nL)))) (+ i 1))
    )  
)
(write (bell (list 1) 10))
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.