Ruby-style iterators

Started by William James, July 04, 2006, 03:50:39 PM

Previous topic - Next topic

William James

My newLISP Sudoku program needed an iterator like this:

each_empty_cell { |row,col|
  . . . .
}

I put the definition in a context to hide the iterator's variables from the lambda it serves.

(context 'each-empty-cell)

(define (each-empty-cell:each-empty-cell func , row col)
  (dotimes (row 9)
    (dotimes (col 9)
      (if (= " " (nth row col MAIN:Board))
        (func row col)))))

(context MAIN)

Example of use:

(each-empty-cell (fn (row col)
  (set 'lst (possibles row col))
  (if (= 1 (length lst))
    (plug-in (first lst) row col))))

Lutz

#1
Technically isolation via a context / namespace is not necessary here. Variable capture can only occur when passing symbols or when using macros. Both is not the case here:



(define (for-each func , row col)
    (dotimes (row 9)
        (dotimes (col 9)
            (func row col))))

(for-each (fn (row col) (println row ":" col)))

0:0
0:1
0:2
...
8:8


but of cause it doesn't harm either ;)



Lutz

William James

#2
(define (for-each func , row col xxx)
  (set 'xxx " oops")
  (dotimes (row 2)
    (dotimes (col 2)
      (func row col))))

(set 'xxx " Correct.")
(for-each (fn (row col) (println row ":" col xxx)))

The output is
0:0 oops
0:1 oops
1:0 oops
1:1 oops


(context 'each-empty-cell)

(define (each-empty-cell:each-empty-cell func , row col xxx)
  (set 'xxx " oops")
  (dotimes (row 2)
    (dotimes (col 2)
      (func row col))))

(context MAIN)

(set 'xxx " Correct.")
(each-empty-cell (fn (row col)
  (println row ":" col xxx)))

The output is
0:0 Correct.
0:1 Correct.
1:0 Correct.
1:1 Correct.

I encountered this problem in the sudoku program, and that's why I used a context.

Another example:
(define (for-each func , row col)
  (dotimes (row 2)
    (dotimes (col 2)
      (func row col))))

(set 'row 8)
(for-each (fn (i j) (println i ":" j " " row)))

Output:
0:0 0
0:1 0
1:0 1
1:1 1

Lutz

#3
Yes, xxx is in the dynamic scope of for-each and any function called by for-each will show the xxx of the caller. No problem here, just a demonstration of dynamic scoping at work ;)



Applied correctly this could save you the passing of parameters via inheriting the scope of the calller in some application.



What I wanted to show in my example, is the behaviour of the variables row and col. Just like xxx, row and col are in the scope of for-each, but the lambda expression (fn (row col ...) creates a a new scope for these variables and is shadowing the definitions of row and col in the scope of the caller. Because of this, row and col did not need context protection, but something like xxx might need it.



The lesson here is: never to use globals (except you really want to), but define all variables in the function where they are used. You can do this putting them in the parameter list after a comma (the comma is just a visual indicator), or more traditionally by using let or its siblings letn and letex. The effect of both methods is the same: creating a new scope for the symbols using lambda expressions.



The difference to lexical scoping is, that in dynamic scoping the scope is open further down into called functions, while in lexical scoped Scheme the scope is closed and not available outside.



Lutz

William James

#4
First, let's see a Ruby iterator in action.

def some_odd_nums
  1.step(9,2) { |n|
    yield n }
end

# ... 586 lines of intervening code

n = 11
some_odd_nums {|i| puts "#{ i } #{ n }" }

Yielding

1 11
3 11
5 11
7 11
9 11


Let's try to achieve the same thing in Chicken Scheme:

(define (some-odd-nums func)
  (let loop ((n 1))
    (if (< n 10)
      (begin
        (func n)
        (loop (+ n 2))))))

; ... 586 lines of intervening code

(define n 11)
(some-odd-nums (lambda (i)
  (print i " " n)))


1 11
3 11
5 11
7 11
9 11

So far, so good.  Now in newLisp:

(define (some-odd-nums func , n)
  (for (n 1 9 2)
    (func n)))

; ... 586 lines of intervening code

(set 'n 11)
(some-odd-nums (fn (i)
  (println i " " n)))

And we see:

1 1
3 3
5 5
7 7
9 9

Not what we wanted.  We assign 11 to n on one line and two lines later n mysteriously becomes something else.  In order to use the iterator safely we have to keep in mind the names of the local variables used in a function 500 lines earlier---clearly intolerable.  We've got to create a "black box" whose internals are hidden and irrelevent.  This calls for a context.

(context 'some-odd-nums)

(define (some-odd-nums:some-odd-nums func , n)
  (for (n 1 9 2)
    (func n)))

(context MAIN)

(set 'n 11)
(some-odd-nums (fn (i)
  (println i " " n)))


1 11
3 11
5 11
7 11
9 11

Eureka.

cormullion

#5
I'm a bit puzzled by that code too, but for different reasons:


(set 'n 11)
(some-odd-nums
   (fn (i) (println i " " n)))


I thought that fn didn't evaluate anything, but just simply assembled a (kind of) list of unevaluated Lisp 'source'. So inside, the 'n' doesn't have any significance or value, any more than the 'i'?. And at the entry to the some-odd-nums function, the value passed to func is also a piece of unevaluated inert Lisp stuff. The 'n' is hibernating, and doesn't know where it will be when it's awakened. When the function is evaluated, the 'n' wakes up, looks for a value, and finds one?



In the same vein, can't you write this:
(for (i 1 10)
(some-odd-nums (fn (i) (println i " " n ))))


because the 'i' inside the fn isn't the same 'i' as the loop iterator?



It may be that my puzzlement is with the way newLISP works, rather than with the way Scheme works... ;-)

Lutz

#6

for (i 1 10)
   (some-odd-nums (fn (i) (println i " " n ))))


The fn expression creates a a new scope for i shadowing the scope of the i from the for loop. The n will take the value of whatever environment it is used in at the moment.



So whenever the (fn (i) ...) expression is called inside some-odd-nums via the func application the i assumes the value passed to func. After func is finished the i will have its old value from the for looping parameter back.



What you are observing is the behaviour of dynamic scoping.



Lutz

cormullion

#7
Thanks, Lutz. I think I was saying that I was more puzzled as to why William wrote that code:


(set 'n 11)
(some-odd-nums
   (fn (i) (println i " " n)))


when, according to my inexperienced eye,  the 'n' wasn't going to pick up the 11, since it was inside the 'fn'. Since Scheme apparently does, but newLISP doesn't, I suppose that we had different expectations of what was 'mysterious'...

Lutz

#8
Quote
according to my inexperienced eye, the 'n' wasn't going to pick up the 11, since it was inside the 'fn'


In dynamic scoping the value of 'n' depends on how th current environment defines it. If 'some-odd-nums' doesn't create a new scope of 'n', then 'n' will also show the value 11. 'fn' only protects 'i' but not 'n'.



Lutz

cormullion

OT
#9
Sudoku in three lines of Perl:



http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html">//http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html



not very readable, though :-)