CODEWITHSUNDEEP
common-lisp
MasterMastic
MasterMastic

Reputation: 21286

How to let a self referential binding?

I have a let and I need one of the bindings to refer to itself in the body. i.e. I need something like this:

(let ((my-value (make-value :some-data 2784 :next-value my-value)))
  ; ...)

This fails because my-value at the definition is unbound. I think I might be able to use setf to assign the value but it's not a good general solution for me (e.g. because of side-effects).

How can I handle this situation? maybe there's a way to have a forward declaration?

Upvotes: 3

Views: 203

Answers (2)

coredump
coredump

Reputation: 38809

I think I might be able to use setf to assign the value but it's not a good general solution for me (e.g. because of side-effects).

Some languages are designed to support self-referential variables, like algebra systems where you can write x = x * 4 - 2 and the system solve your equation for x. In Common Lisp the evaluation rules say that you must be able to evaluate x in the arguments of make-value before being able to assign a meaningful value to x.

You could delay operations with a lambda. For example, you could add a lazy-let macro which would transform this:

(lazy-let ((x (make-value :some-data d :next-value x)))
  ...)

... into that:

(let* ((x0 nil)
       (x (make-value :some-data d :next-value (lambda () x0))))
  (setf x0 x)
  ...)

But then you would need to force the lazy value to be computed, with a funcall. Lazy languages like Haskell hide this behavior for you.

If you were writing in Prolog, you would say:

make_value(X,D) :- X = value{data: D, next: X}.

This works thanks to unification, which among other things can be used to perform an interesting kind of side-effects, namely setting a variable at most once. This, however, is not possible directly in Common Lisp (you can implement unification in Lisp, but you should probably not if the sole purpose is to avoid setf).

What happens in the above examples is that side-effects are hidden. My point is that there is nothing magic: somehow, there must be a side-effect to establish a link between an object and itself, even if it is not visible.

You can do the same and provide a side-effect free function over an implementation which locally perform side-effects. That's perfectly acceptable. First, define your type:

(defstruct (value (:constructor make-value%))
  some-data
  next-value)

The basic constructor is named make-value%, a name which should probably not be exported by your package. Then, you define the user-facing constructor: 

(defun make-value (&key some-data (next nil nextp))
  (let ((value (make-value% :some-data some-data)))
    (setf (value-next-value value) (if nextp next value))
    value))

The implementation carefully wraps a local side-effect into a function which, from an external point of view, does not mutate its environment (remark: allocating memory is a side effect too). It allows the user to provide a next element, but by default it links the structure to itself. Here is an example usage:

(let ((x (make-value :some-data 1234)))
  (assert (eq x (value-next-value x))))

Upvotes: 9

sds
sds

Reputation: 60014

You should follow the advice from the commenters and create the object and then modify it:

(setq *print-circle* t)
(let ((x (list 1 2 3)))
  (setf (second x) x)
  x)
==> #1=(1 #1# 3)

If you really want to go crazy, you can use the reader magic:

(let ((x '#1=(1 #1# 3)))
  x)
==> #1=(1 #1# 3)

However, this creates a quoted object, which you should not modify later.

It will also create a unique object, i.e., if not a fresh object, i.e., each invocation of the above code will return the same object:

(defun unsafe ()
  '#1=(1 #1# 3))
(eq (unsafe) (unsafe))
==> T

Upvotes: 4

Related Questions