I'm trying to implement back-tracking search in Scheme. So far, I have the following:
(define (backtrack n graph assignment)
(cond (assignment-complete n assignment) (assignment) )
(define u (select-u graph assignment))
(define c 1)
(define result 0)
(let forLoop ()
(when (valid-choice graph assignment c)
(hash-set! assignment u c)
(set! result (backtrack n graph assignment))
(cond ((not (eq? result #f)) result))
(hash-remove! assignment u)
)
(set! c (+ c 1))
(when (>= n c) (forLoop))
)
#f ; I believe this is where I'm having problems
)
My functions assignment-complete and select-u pass unit tests. The argument assignment is a hash-table make with (make-hash), so it should be fine.
I believe the problem I have is related to returning false at the end of the loop, if no recursive returns a non-false value (which should be a valid assignment). Is there a Scheme equivalent of an explicit return statement?
the answer to your question is yes:
(define (foo ...)
(call-with-current-continuation
(lambda (return)
...... ; here anywhere inside any sub-expression
...... ; you can call (return 42)
...... ; to return 42 from `foo` right away
)))
This sets up an exit continuation so that you can return a result value from inside a function's body. The usual Scheme way is to put your return form as the last one, so its value is returned:
(let forLoop ()
(when (valid-choice graph assignment c)
(hash-set! assignment u c)
(set! result (backtrack n graph assignment))
(cond
((not (eq? result #f))
result)) ; the value of `cond` form is ignored
(hash-remove! assignment u))
; the value of `when` form is ignored
(set! c (+ c 1))
(if (>= n c) ; `if` must be the last form
(forLoop) ; so that `forLoop` is tail-recursive
;; else:
return-value) ; <<------ the last form's value
) ; is returned from `let` form
;; (let forLoop ...) must be the last form in your function
;; so its value is returned from the function
)
You also have a problem here:
(cond (assignment-complete n assignment) (assignment) )
this code does not make a call (assignment-complete n assignment)
. Rather, it checks whether a variable assignment-complete
has a non-null value, and if not it checks assignment
variable, but in any case its returned value is just ignored anyway. Perhaps some more parentheses are missing there, and/or an else
clause.