ESP32 core crash in recursive calculation

#1

Hello,
I use uLisp version 3.0a on an M5Stack (ESP32). To refresh my Lisp knowledge I’m hanging around with the book “Structure and Interpretation of Computer Programs”. One example leads to a core crash:

(defun sum (term a next b)
  (if (> a b)
      0
    (+ (term a)
       (sum term (next a) next b))))

(defun cubic (x) (* x x x))

(defun inc (n) (+ n 1))

(defun cubic-sum (a b)
  (sum cubic a inc b))

The cubic sum from 1 to 10 is calculated correctly:

7894> (cubic-sum 1 10)
3025

Even from 1 to 100 it works as expected:

7894> (cubic-sum 1 100)
25502500

But with higher values a core crash occurs:

7920> (cubic-sum 1 200)
Guru Meditation Error: Core 1 panic’ed (Unhandled debug exception)
Debug exception reason: Stack canary watchpoint triggered (loopTask)

I have tried the square sum instead of the cubic sum, but the error occurs identically. I have also recursively calculated the faculty of large numbers without causing such an error.
What could that be?

#2

I think you’re simply overflowing the stack. uLisp attempts to detect that situation, but it’s not always possible.

To refresh my Lisp knowledge I’m hanging around with the book “Structure and Interpretation of Computer Programs”.

One of my favourite Lisp books - let us know how you get on!

#3

I only started learning lisp the last few months, I found uLisp awesome. I am actually reading Common lisp a gentle introduction to symbolic computation but I have Structure and interpretation of computer programs which one of the next books on my list.

(defun sum (term a next b)
	(if (> a b)
		0
		(+ (term a)
			(sum term (next a) next b))))

I think the book you are reading is on Scheme, and I am using common Lisp and uLisp so shouldn’t you need to use funcall to call the term and next functions? Also I can’t even define that function in common lisp it fails completely causing stack overflow I think if it’s because of the recursion where you call sum again because there is no condition to stop.

#4

You’re correct; in Common Lisp you’ll need to write:

(defun sum (term a next b)
  (if (> a b)
      0
    (+ (funcall term a)
       (sum term (funcall next a) next b))))

(defun cubic (x) (* x x x))

(defun inc (n) (+ n 1))

(defun cubic-sum (a b)
  (sum #'cubic a #'inc b))

because Common Lisp has separate symbols for functions and variables. That should then work:

> (cubic-sum 1 10)
3025

Either version will work fine in uLisp.

#5

Aha so my intuition was right it works, this will help Hague

#6

By the way, uLisp provides Tail-Call Optimization, so a properly optimized tail-recursive function will be converted to a non-recursing loop and will never run out of stack space.

In your example the function sum isn’t tail-recursive, because the recursive call to sum is one of the arguments to +.

It’s usually possible to rewrite a function recursively, by adding one argument, the accumulator, which saves all the state that we want to pass forward. Here’s how you can do it with this function; the accumulator is called res:

(defun sum (term a next b res)
  (if (> a b)
      res
    (sum term (next a) next b (+ (term a) res))))

(defun cubic (x) (* x x x))

(defun inc (n) (+ n 1))

(defun cubic-sum (a b)
  (sum cubic a inc b 0))

For more information see Paul Graham’s “On Lisp”, section 2.8, available online at http://www.paulgraham.com/onlisptext.html.

Now cubic-sum is properly tail-recursive and doesn’t run out of stack space, even with much larger arguments:

> (cubic-sum 1 300)
2038522500