CODEWITHSUNDEEP
recursioncommon-lisp
paranoid_android
paranoid_android

Reputation: 77

Variable Not A Number Error in Lisp (Which is not true)

I have a code which takes a list and returns all possible permutations by the parameter result. But when I compile I have an error which says *** - =: (1+ INDEX) is not a number. Is this message true or I messed up the code generally? I am new to lisp I can looking for a fix and also open to suggestions from fucntional programmers.

;; Creates permutatiions of a given list and returns it via parameter
(defun create-permuations (source)
  (setf result (list))
  (create-permuations-helper source 0 '() result)
  result)

(defmacro create-permuations-helper (source index cur result)
  (if (= (list-length cur) index)
      (cons cur result)
      (loop for i from 0 to (list-length cur) do
        (create-permuations-helper source (1+ index)
                                   (append cur (list (nth i source))) result))))

Upvotes: 1

Views: 435

Answers (1)

coredump
coredump

Reputation: 38809

99% of times when a compiler reports an error you can trust it to be true. Here Index is the list (1+ index), literally the 1+ symbol followed by the index symbol. This is so because you are using a macro, and macros operate on code.

In your macro, you do not return a form to be evaluated, you execute code during macro-expansion that depends on itself. That alone is an undefined behaviour. For example:

(defmacro a (x)
  (if (plusp x)
      (a (- x 1))
      nil))

In the body of a, you want to expand code using a recursive call to itself. But the macro is not yet fully known and cannot be until the whole macro is defined.

Maybe the particular lisp implementation binds a to the macro function in body of the macro, which is a strange thing to do, or you evaluated the definition twice. The first time the compiler assumes a is an unknown function, then binds a to a macro, and the second time it tries to expand the macro. Anyway macro are not supposed to be recursive.

In the example, since the macro does not evaluate its argument, the nested call to the macro is given the literal expression (- x 1), and not its actual value, which cannot be known anyway since x is unknown. You are crossing a level of abstraction here by trying to evaluate things at macroexpansion time.

But, macros can expand into code that refers to themselves.

(defmacro a (x)
  (if (plusp x)
      `(b (a ,(- x 1)))
      nil))

Now, (a 2) expands into (b (a 1)), which itself macroexpands into (b (b (a 0))), and finally reaches a fixpoint which is (b (b nil)).

The difference is that the macro produces a piece of code and returns, which the compiler macroexpands again, whereas in the first example, the macro must already be expanded in the body of its own definition.

Possible implementation

One way to solve your problem is to define a local function that has access to a variable defined in your main function. Then, the local function can set it, and you do not need to pass a variable by reference (which is not possible to do):

(defun permut (list)
  (let (result)
    (labels ((recurse (stack list)
               (if list
                   (dolist (x list)
                     (recurse (cons x stack)
                              (remove x list :count 1)))
                   (push stack result))))
      (recurse nil list))
    result))

Alternatively, you can split the process in two; first, define permut-helper, which is a higher-order function that takes a callback function; it generates permutations and calls the callback for each one:

(defun permut-helper (stack list callback)
  (if list
      (dolist (x list)
        (permut-helper (cons x stack)
                       (remove x list :count 1)
                       callback))
      (funcall callback stack)))

You call it with a function that pushes results into a list of permutations:

(defun permut (list)
  (let (result)
    (flet ((add-result (permutation)
             (push permutation result)))
      (permut-helper nil list #'add-result))
    result))

Upvotes: 3

Related Questions