Ruby-style iterators

[William James]

My newLISP Sudoku program needed an iterator like this:

Code Select Expand


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

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

Code Select Expand


(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:

Code Select Expand


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


[Lutz]

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:

Code Select Expand


(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]

Code Select Expand

(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

Code Select Expand

0:0 oops
0:1 oops
1:0 oops
1:1 oops

Code Select Expand

(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

Code Select Expand

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:

Code Select Expand

(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:

Code Select Expand

0:0 0
0:1 0
1:0 1
1:1 1

[Lutz]

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]

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

Code Select Expand


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

Code Select Expand


1 11
3 11
5 11
7 11
9 11


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

Code Select Expand


(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)))


Code Select Expand


1 11
3 11
5 11
7 11
9 11

So far, so good.  Now in newLisp:

Code Select Expand


(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:

Code Select Expand


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.

Code Select Expand


(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)))


Code Select Expand


1 11
3 11
5 11
7 11
9 11

Eureka.

[cormullion]

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

Code Select Expand

(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:

Code Select Expand

(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]

Code Select Expand


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]

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

Code Select Expand

(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]

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]

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 :-)