I'd like to know how to optimize this by shadowing symbols 'lo and 'hi inside nested function f. I guess CPS conversion would solve this but how?

;; chess engine - early development

;; Alist: (cons 'piece xy-coordinates)
(define whites) (define blacks)

  (define setup
    (let ([lo `(p0 p1 p2 p3 p4 p5 p6 p7)]
            [hi `(r0 n0 b0 q k b1 n1 r1)])
      (define f
        (let ([xs (iota 8)])
          (lambda (ls y)
            (map (lambda (i x) (cons i (cons x y))) ls xs))))
      (lambda (l h) (concatenate (f lo l) (f hi h)))))
  (set! whites (setup 1 0)) (set! blacks (setup 6 7)))

Your question and code are both confusing to me, but I'll give it a shot.

(define whites) doesn't compile with my standard definition of define. define usually needs to bind the identifier to something, even if it is just '() or #f. Since it seems like they (blacks and whites) are meant to hold a-lists, I've initialized them to '().

I don't know what dialect of scheme you're running, but you may be able to drop the outer begin form, and your concatenate function is usually called append in most schemes. Finally, you may have a list* function so to replace (cons i (cons x y)) with (list* i x y)

Next, in order to call setup, it wasn't immediately clear that setup was a function that took two arguments, the first being an integer intended to be the row to place the pieces onto, and the second being the row to set the pawns. I would make setup into a thunk since the initial placement of the pieces is pretty intrinsic to chess unless you're planning to support rectangular boards or something. Also, being a thunk emphasizes that it's being called for its side effect, and not it's value. You could really bring home that point by calling the function setup! instead.

I would give more descriptive names to your identifiers. I would create a function that put a list of pieces together with their coordinates, called make-row, and a function that setup both the pieces and pawns given the rows to place them on, called setup-color

With regard to your concern about optimizing: readability and extensibility are usually more important than a few instructions. There are exceptions, and those exceptions will kill performance if you don't optimize when they occur. There are no rules about where performance bottlenecks lie, except for they are usually not where you think they are ;-). That's why it is important to MEASURE your performance as you go. The bottlenecks of most chess engines are usually NOT in the method used to setup the board. They are usually in the search methods, so when you get there, time spent optimizing will yield a much better ROI.

Also, when you go to optimize, before starting down the path of flipping your program inside -out to CPS it, consider easier wins first, like using a vector instead of a list as your primary data structure.

As for shadowing symbols, it seems you may have a misunderstanding. Shadowing doesn't buy you anything in performance. It's not the identifier that takes up space, it's whatever that identifier is bound to. When you shadow a variable, the old value still has to be stored for when it is unshadowed later.

In fact, shadowing variables can actually be harmful to performance in some cases. Since you can shadow primitive operations like +, the compiler is unable to safely inline those operations. If you can tell the compiler that you promise not to shadow +, it can inline addition operations. If your implementation has a decent module system, wrapping you code in modules may help the compiler make these deductions, otherwise there may be flags to encourage inlining.

Here is my suggested refactoring.

;; Alist: (cons 'piece xy-coordinates)
(define whites '())
(define blacks '())

;;Set!s whites and blacks to the initial chessboard setup
(define (setup!)
  (define (make-row pieces row)
    (map (lambda (piece x) (list* piece x row)) 
     (iota 8)))

  (define (setup-color pawn-row piece-row)
    (let ((pawns '(p0 p1 p2 p3 p4 p5 p6 p7))
          (pieces '(r0 n0 b0 q k b1 n1 r1)))
       (make-row pawns pawn-row)
       (make-row pieces piece-row))))

  (set! whites (setup-color 1 0))
  (set! blacks (setup-color 6 7)))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.