Quantcast

Maximum PC

It is currently Sat Sep 20, 2014 2:30 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Conway's game of life in Python
PostPosted: Sat May 21, 2011 1:31 pm 
8086
8086

Joined: Thu Jul 30, 2009 7:49 am
Posts: 74
I've been trying to create a simple implementation of Conway's Game of Life in Python. I have a logic error somewhere, but cannot seem to find it. I think it's in the process method, and it probably has something to do with my looping structures. Any help would be appreciated.
Code:
import random
#import time
random.seed()
def initialize():
    display = [[None] * 80] * 25
    display=[[random.getrandbits(1) for cell in line] for line in display]
    return display
def process(display):#error in this function
    buffer = [[None] * 80] * 25
    a = [(x,y) for x in (-1,0,1) for y in (-1,0,1)]
#create a list of 2d offsets
    a.remove((0,0)) #remove working cell
    x1=0
    y1=0#start in upper left corner
    for line in display:
        for cell in line:
            b=a[:]#copy to avoid changing original
            #remove offsets if on edge of grid
            if x1==0:
                b.remove((-1,-1))
                b.remove((-1,0))
                b.remove((-1,1))
            if x1==79:
                b.remove((1,-1))
                b.remove((1,0))
                b.remove((1,1))
            if y1==0:
                b.remove((0,-1))
                try:
                    b.remove((1,-1))
                except ValueError:
                    pass
                try:
                    b.remove((-1,-1))
                except ValueError:
                    pass
            if y1==24:
                b.remove((0,1))
                try:
                    b.remove((-1,1))
                except ValueError:
                    pass
                try:
                    b.remove((1,1))
                except ValueError:
                    pass
            surround = []
            for (x,y) in b:
                    surround.append(display[y1+y][x1+x])
            number = sum(surround)#count surounding live cells
            if number == 3:#cell is alive
                buffer[y1][x1] = 1
            elif number == 2:#cell maintains state
                buffer[y1][x1] = display[y1][x1]
            else:#cell is dead
                buffer[y1][x1] = 0
            x1 += 1
        y1 += 1
        x1=0
    return buffer
def output(buffer):
    display = [[None] * 80] * 25
    x1=0
    y1=0
    for line in buffer:
        for cell in line:
            print(cell, end='')
            display[y1][x1]=cell
            x1 += 1
        y1 += 1
        x1=0
    return display
def live():
    for line in display:
        for cell in line:
            if cell:
                return True
                break
        else:
            return False
display=initialize()
output(display)
#time.sleep(1)
while live():
    buffer=process(display)
#   time.sleep(1)
    display=output(buffer)


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Sat May 21, 2011 8:49 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
What have you done to fix it? What sort of logic error?

I don't have time to figure out your logic issues.

Is this homework?


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Sun May 22, 2011 7:12 am 
8086
8086

Joined: Thu Jul 30, 2009 7:49 am
Posts: 74
No, it is not homework, personal project. I'm self taught and this is my first python script.
The first, randomly generated iteration works fine. In the next iteration, each row is the same. I have not been able to see what it is doing in between the first and second round, afterward, any cell surrounded on both sides of the repeated row dies, as do single cells, eventually leaving columns of two that do not die/move.
My approach is to cycle through each cell in each row, poll the surrounding cells, and sum them. The corresponding cell in the buffer is assigned a value accordingly. 3=dead, 2= same, else dead. Obviously, this is not what's happening. Any help lining up what I mean and what my code says?


EDIT: after more debugging, I found out
Code:
buffer = [[None]*8]*25
creates a whole lot of shared references. Not what I want.
redoing those loops in a bit, changing to while and defining buffer as empty, then appending.


Working Code:
Code:
import random
random.seed()

def initialize():
    display = [[None] * 80] * 25
    display=[[random.getrandbits(1) for cell in line] for line in display]
    return display

def process(display):#error in this function
    buffer=[]
    a = [(x,y) for x in (-1,0,1) for y in (-1,0,1)]
    a.remove((0,0))
    x1=0
    y1=0
    while y1 <25:
        buffer.append([])
        while x1<80:
            b=a[:]
            if x1==0:
                b.remove((-1,-1))
                b.remove((-1,0))
                b.remove((-1,1))
            if x1==79:
                b.remove((1,-1))
                b.remove((1,0))
                b.remove((1,1))
            if y1==0:
                b.remove((0,-1))
                try:
                    b.remove((1,-1))
                except ValueError:
                    pass
                try:
                    b.remove((-1,-1))
                except ValueError:
                    pass
            if y1==24:
                b.remove((0,1))
                try:
                    b.remove((-1,1))
                except ValueError:
                    pass
                try:
                    b.remove((1,1))
                except ValueError:
                    pass
            surround = []
            for (x,y) in b:
                    surround.append(display[y1+y][x1+x])
            number = sum(surround)
            if number == 3:
                buffer[y1].append(1)
            elif number == 2:
                buffer[y1].append(display[y1][x1])
            else:
                buffer[y1].append(0)
            x1 += 1
        y1 += 1
        x1=0
    return buffer

def output(buffer):
    display = []
    i=0
    for line in buffer:
        display.append([])
        for cell in line:
            print(cell, end='')
            display[i].append(cell)
        i += 1
    return display

def live():
    for line in display:
        for cell in line:
            if cell:
                return True
                break
        else:
            return False

display=initialize()
output(display)
while live():
    buffer=process(display)
    display=output(buffer)


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Sun Jun 19, 2011 8:52 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Hey freak702... I just want to point out some things that you can do to improve your program (and programming). First, your code is hard to understand: 90% of the code is in a single function, you have NO COMMENTS AT ALL, and you've chosen some rather vague names for your functions. It's one thing to omit comments in a function named dfsSearch or mergeSort, but quite another in a function named algorithm or search... or process (which is actually misleading because usually functions with process in their name have something to do with concurrency). ;)

Also, it isn't clear that how your program relates to the actual rules in Conway's Game of Live:

Wikipedia wrote:
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.


Below is a Common Lisp grid/matrix version of the game. Don't worry trying to understand all of the language (I didn't use any advanced language features, so it shouldn't be hard to follow). Notice that I have chosen to expand the grid by two rows and columns so that I don't need to check for the out of bounds conditions. This also makes counting the number of neighbors easier.

Also, it appeared that you were having some trouble with referencing the grid correctly. It is often easy to correct (or completely avoid) these types of errors by writing your program in a 'functional style'. You'll see an example of this in my next-grid function which accepts the current grid, then generates a new grid with each function call. No state, no errors. Sure, it uses more memory than either an in-place version or trying to alternate between two grids, but using a matrix is already horribly inefficient (think 10000x10000 sized grids) and doesn't allow you to expand indefinitely like in the real game.

I also added some code to check for a 'stabilized pattern', max number of iterations, etc. The main game code is below. Also notice that I've nested 3 functions inside my main function which is a common technique in languages that support it for creating 'private functions' (the inspiration for public/private access in the OOP world).

Code:
;;The following is all the code needed to run the game, but it requires
;;the user to provide it with an inital grid configuration.  I've decided
;;to add additional rows and cols around the grid which is a pretty common
;;technique in proramming contests/simple programs for eliminating error checks.
(defun game-of-life (grid &optional (max-iterations 20))
  "Runs an instance of Conway's Game of Life."
  (let ((halt-game nil))

    (defun next-grid (grid)
      "Given a grid, returns the next 'tick' in the game."
      (let ((new-grid (make-array (array-dimensions grid) :initial-element 0)))
   (loop for r from 1 to (- (array-dimension grid 0) 2) do
         (loop for c from 1 to (- (array-dimension grid 1) 2) do
          (let ((num-live (num-live-neighbors grid r c)))
            (cond ((or (< num-live 2) (> num-live 3))         ;Rules 1 & 3
              (setf (aref new-grid r c) 0))
             ((and (= (aref grid r c) 0) (= num-live 3)) ;Rule 3
              (setf (aref new-grid r c) 1))
             (t (setf (aref new-grid r c) (aref grid r c))))))) ;Rule 2 & default behavior
   (if (equalp grid new-grid)
     (setf halt-game t))
   new-grid))

    (defun num-live-neighbors (grid row col)
      "Returns the number of live neighbors in adjacent cells of the grid."
      (let ((above (1- row))
       (below (1+ row))
       (left (1- col))
       (right (1+ col)))
   (+ (aref grid above left) (aref grid above col) (aref grid above right)
      (aref grid row left)                         (aref grid row right)
      (aref grid below left) (aref grid below col) (aref grid below right))))

    (defun print-grid (grid iteration &optional (alive-char #\X) (dead-char #\.))
      (format t "Iteration #~a~%" iteration)
      (loop for r from 1 to (- (array-dimension grid 0) 2) do
       (loop for c from 1 to (- (array-dimension grid 1) 2) do        
        (format t "~a" (if (= (aref grid r c) 1)
                 alive-char
                 dead-char)))
       (format t "~%"))
      (format t "~%"))

    ;;this is the actual game loop
    (print-grid grid 0)
    (loop for i from 1 to max-iterations
     unless halt-game do
     (setf grid (next-grid grid))
     (if halt-game
         (format t "The game stabilized after ~r iterations.~%" i))
     (print-grid grid i))
    halt-game))


I also wrote a couple of helper functions to create the grids and hard-coded a few interesting starting configurations from wikipedia.

Code:
;;The following are helper functions used to setup an initial grid.
(defun random-game (rows cols &optional (max-iterations 20))
  "Starts the game using a randomly generated grid of a given size."
  (defun seed-grid (grid)
    "Randomly seeds the initial grid with values of 0 or 1."
    (loop for r from 1 to (- (array-dimension grid 0) 2) do
     (loop for c from 1 to (- (array-dimension grid 1) 2) do
      (setf (aref grid r c) (random 2))))
    grid)
  (game-of-life (seed-grid (make-grid (list rows cols))) max-iterations))

(defun make-grid (dimensions &optional (contents nil))
  "I am using the extra row and col technique to simplify error checking
   in the num-live-neighbors function (ie a call to this function with
   num-rows and num-cols equal to 10 will return a 12x12 array)."
  (let ((grid (make-array (mapcar (lambda (n) (+ n 2)) dimensions) :initial-element 0)))
    (unless (eq contents nil)
      (loop for row in contents
       for r from 1 do
       (loop for element in row
        for c from 1 do
        (setf (aref grid r c) element))))
    grid))


;;The following starting configurations are known as "still lives".
(setf block (make-grid '(4 4) '((0 0 0 0)
            (0 1 1 0)
            (0 1 1 0)
            (0 0 0 0))))

(setf beehive (make-grid '(5 6) '((0 0 0 0 0 0)
              (0 0 1 1 0 0)
              (0 1 0 0 1 0)
              (0 0 1 1 0 0)
              (0 0 0 0 0 0))))

(setf loaf (make-grid '(6 6) '((0 0 0 0 0 0)
                (0 0 1 1 0 0)
                (0 1 0 0 1 0)
                (0 0 1 0 1 0)
                (0 0 0 1 0 0)
                (0 0 0 0 0 0))))

(setf boat (make-grid '(5 5) '((0 0 0 0 0)
                (0 1 1 0 0)
                (0 1 0 1 0)
                (0 0 1 0 0)
                (0 0 0 0 0))))

;;Oscillators
(setf blinker (make-grid (list 5 5) '((0 0 0 0 0)
                  (0 0 1 0 0)
                  (0 0 1 0 0)
                  (0 0 1 0 0)
                  (0 0 0 0 0))))

(setf toad (make-grid '(6 6) '((0 0 0 0 0 0)
                (0 0 0 0 0 0)
                (0 0 1 1 1 0)
                (0 1 1 1 0 0)
                (0 0 0 0 0 0)
                (0 0 0 0 0 0))))

(setf beacon (make-grid '(6 6) '((0 0 0 0 0 0)
             (0 1 1 0 0 0)
             (0 1 1 0 0 0)
             (0 0 0 1 1 0)
             (0 0 0 1 1 0)
             (0 0 0 0 0 0))))

(setf pulsar (make-grid '(17 17) '((0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
               (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))))

;;"block-laying switch engines"
(setf indef1 (make-grid '(7 7) '((0 0 0 0 0 0 0)
             (0 1 1 1 0 1 0)
             (0 1 0 0 0 0 0)
             (0 0 0 0 1 1 0)
             (0 0 1 1 0 1 0)
             (0 1 0 1 0 1 0)
             (0 0 0 0 0 0 0))))

(setf indef2 (make-grid '(8 10) '((0 0 0 0 0 0 0 0 0 0)
              (0 0 0 0 0 0 0 1 0 0)
              (0 0 0 0 0 1 0 1 1 0)
              (0 0 0 0 0 1 0 1 0 0)
              (0 0 0 0 0 1 0 0 0 0)
              (0 0 0 1 0 0 0 0 0 0)
              (0 1 0 1 0 0 0 0 0 0)
              (0 0 0 0 0 0 0 0 0 0))))


HTH's ... I'll post a followup with some of the configurations running.


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Sun Jun 19, 2011 8:54 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
The pulsar at the end is pretty cool. Hopefully the forum doesn't destroy the formatting.
Code:
CL-USER> (game-of-life beehive 100)
Iteration #0
......
..XX..
.X..X.
..XX..
......

The game stabilized after one iterations.
Iteration #1
......
..XX..
.X..X.
..XX..
......


CL-USER> (game-of-life blinker 10)
Iteration #0
.....
..X..
..X..
..X..
.....

Iteration #1
.....
.....
.XXX.
.....
.....

Iteration #2
.....
..X..
..X..
..X..
.....

Iteration #3
.....
.....
.XXX.
.....
.....

Iteration #4
.....
..X..
..X..
..X..
.....

Iteration #5
.....
.....
.XXX.
.....
.....

Iteration #6
.....
..X..
..X..
..X..
.....

Iteration #7
.....
.....
.XXX.
.....
.....

Iteration #8
.....
..X..
..X..
..X..
.....

Iteration #9
.....
.....
.XXX.
.....
.....

Iteration #10
.....
..X..
..X..
..X..
.....


CL-USER> (game-of-life pulsar 6)
Iteration #0
.................
.................
....XXX...XXX....
.................
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
....XXX...XXX....
.................
....XXX...XXX....
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
.................
....XXX...XXX....
.................
.................

Iteration #1
.................
.....X.....X.....
.....X.....X.....
.....XX...XX.....
.................
.XXX..XX.XX..XXX.
...X.X.X.X.X.X...
.....XX...XX.....
.................
.....XX...XX.....
...X.X.X.X.X.X...
.XXX..XX.XX..XXX.
.................
.....XX...XX.....
.....X.....X.....
.....X.....X.....
.................

Iteration #2
.................
.................
....XX.....XX....
.....XX...XX.....
..X..X.X.X.X..X..
..XXX.XX.XX.XXX..
...X.X.X.X.X.X...
....XXX...XXX....
.................
....XXX...XXX....
...X.X.X.X.X.X...
..XXX.XX.XX.XXX..
..X..X.X.X.X..X..
.....XX...XX.....
....XX.....XX....
.................
.................

Iteration #3
.................
.................
....XXX...XXX....
.................
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
....XXX...XXX....
.................
....XXX...XXX....
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
.................
....XXX...XXX....
.................
.................

Iteration #4
.................
.....X.....X.....
.....X.....X.....
.....XX...XX.....
.................
.XXX..XX.XX..XXX.
...X.X.X.X.X.X...
.....XX...XX.....
.................
.....XX...XX.....
...X.X.X.X.X.X...
.XXX..XX.XX..XXX.
.................
.....XX...XX.....
.....X.....X.....
.....X.....X.....
.................

Iteration #5
.................
.................
....XX.....XX....
.....XX...XX.....
..X..X.X.X.X..X..
..XXX.XX.XX.XXX..
...X.X.X.X.X.X...
....XXX...XXX....
.................
....XXX...XXX....
...X.X.X.X.X.X...
..XXX.XX.XX.XXX..
..X..X.X.X.X..X..
.....XX...XX.....
....XX.....XX....
.................
.................

Iteration #6
.................
.................
....XXX...XXX....
.................
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
....XXX...XXX....
.................
....XXX...XXX....
..X....X.X....X..
..X....X.X....X..
..X....X.X....X..
.................
....XXX...XXX....
.................
.................


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Fri Jul 15, 2011 12:27 pm 
8086
8086

Joined: Thu Jul 30, 2009 7:49 am
Posts: 74
I've split up and renamed some functions, and added comments. I know the rules call for an infinite grid, but I'm just making this to practice Python and see a pattern of 1's and 0's on the console, so I've limited the grid to the default Windows command prompt size. More Conway's Petri Dish, I suppose. I might add more features later (output settings, use predefined grids, etc.).

Code:
import random
import copy
random.seed()

#creates a list of (x,y) offsets
a = [(x,y) for x in (-1,0,1) for y in (-1,0,1)]
a.remove((0,0))

#returns a random game grid
def initialize():
    display = [[None] * 80] * 25
    display=[[random.getrandbits(1) for cell in line] for line in display]
    return display

#counts living neighbors of cell (x1,y1) in grid display
def count_live_neighbors(display, x1, y1):
    b=a[:]
    #romove offsets if on edge of grid to avoid list bounding errors
    if x1==0:
        b.remove((-1,-1))
        b.remove((-1,0))
        b.remove((-1,1))
    elif x1==79:
        b.remove((1,-1))
        b.remove((1,0))
        b.remove((1,1))
    if y1==0:
        b.remove((0,-1))
        try:
            b.remove((1,-1))
        except ValueError:
            pass
        try:
            b.remove((-1,-1))
        except ValueError:
            pass
    elif y1==24:
        b.remove((0,1))
        try:
            b.remove((-1,1))
        except ValueError:
            pass
        try:
            b.remove((1,1))
        except ValueError:
            pass
    #create a list of surrounding cells
    surround = []
    for (x,y) in b:
        surround.append(display[y1+y][x1+x])
    #return the number of living cells
    return sum(surround)

#accepts a game grid and returns the next cycle in the game
def next_tick(display):
    buffer=[]
    x1=0
    y1=0
    while y1 <25:
        buffer.append([])
        while x1<80:
            number = count_live_neighbors(display, x1, y1)
            if number == 3:
                buffer[y1].append(1)
            elif number == 2:
                buffer[y1].append(display[y1][x1])
            else:
                buffer[y1].append(0)
            x1 += 1
        y1 += 1
        x1=0
    return buffer

#prints the game grid
def output(buffer):
    for line in buffer:
        for cell in line:
            print(cell, end='')

#determines whether or not any cells are alive
def live():
    for line in display:
        for cell in line:
            if cell:
                return True
                break
        else:
            return False

#game loop
display=initialize()
output(display)
while live():
    buffer=next_tick(display)
    output(buffer)
    display=copy.deepcopy(buffer)


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Sun Jul 17, 2011 8:02 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
freak720 wrote:
I've split up and renamed some functions, and added comments.

Much better! =)


Code:
#creates a list of (x,y) offsets
a = [(x,y) for x in (-1,0,1) for y in (-1,0,1)]
a.remove((0,0))

I prefer using an oversized grid and array indices like above, below, left and right; I guueeessssss this is passable solution. =)

Code:
#determines whether or not any cells are alive
def live():
    for line in display:
        for cell in line:
            if cell:
                return True
                break
        else:
            return False

This might not work as intended. Sure, it tells you whether or not there are any live cells; However, you can reach states in the game where there are live cells, but they're never going to change, so you'll be stuck in an infinite loop.


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Thu Jul 21, 2011 1:00 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Hey Freak720... how is your knowledge of functional programming idioms in Python? I'm starting to work on some software for derivatives trading/pricing and might need to port some code to Python for use with Sage (a mathematical interface to several open source mathematical packages written in Python).

Can/Do you know how to do the following?
1. Define function arguments using keywords, optional values, multi-length args, etc.
Code:
CL-USER> (defun foo (&key (date "jan 1") price (quantity 100))
      (format t "date: ~a  price: ~a  quantity: ~a~%" date price quantity))
FOO
CL-USER> (foo :date "jan 2" :price 1 :quantity 10)
date: jan 2  price: 1  quantity: 10
CL-USER> (foo :price 1)
date: jan 1  price: 1  quantity: 100
CL-USER> (foo :price 1 :date "jan 10")
date: jan 10  price: 1  quantity: 100


2. Pass a function as an argument. Define a function that accepts a function as an arguement.
Code:
;;built in function sort in Lisp
(sort '(2 3 1 4 5) #'<)

In Common Lisp, functions and symbols have different namespaces. The #' is used to indicate the function namespace. For example, if I type #'< at the prompt by itself (ie similar to how you would type a variable name to find the value of the variable), the REPL replies with
Code:
CL-USER> #'+
#<SYSTEM-FUNCTION +>

When defining a function, you need to call it using the funcall function (CL is a bit messier then Scheme in this respect where you just use the function name)...
Code:
CL-USER> (defun do-op (op a b)
      (funcall op a b))
DO-OP
CL-USER> (do-op #'+ 1 2)
3
CL-USER> (do-op #'* 1 2)
2


2. Use mapping functions.
I know that you can do some things without having to call a map function in Python. For example, if I have a list of integers lst, I can use lst*2 to multiply the contents by 2. The reason I ask is that Lisp (and Python) programmers tend to make heavy use of mapping functions (ie applicative programming as opposed to iterating all over the place with loops). I'm kind of curious how Python compares...
Code:
CL-USER> (mapcar #'+ '(1 2 3) '(10 20 30))
(11 22 33)
CL-USER> (mapcar #'(lambda (n)
           (if (evenp n)
          (* n 10)
          n)) ;else just return n
       '(1 2 3 4 5))
(1 20 3 40 5)

I think that I'm going to be making heavier than normal use of mapping function for time-series data, profits for various stock prices, and plotting graphs in Sage. One of the things that was giving me trouble while working with Sage involves the min and max functions. I need to be able to do something like the following...
Code:
CL-USER> (mapcar (lambda (x) (max 0 x)) '(-2 -1 0 1 2))
(0 0 0 1 2)

3. Return a function.
At the moment, I'm thinking through the design, but one of the options that I'm considering includes writing a function that returns a function based on some input parameters. This is a toy example, but I'd like to know if it can be done...
Code:
CL-USER> (defun my-adder (amount)
      "Returns a function that increments the input parameter by amount."
      #'(lambda (n) (+ n amount)))
MY-ADDER
CL-USER> (setf add3 (my-adder 3))
#<FUNCTION :LAMBDA (N) (+ N AMOUNT)>
CL-USER> (funcall add3 10)
13


4. Taking the previous example a step further, can you enclose a function (ie a function closure).
Code:
CL-USER> (defun enclosure-adder (amount)
      "Returns a function that increments the input parameter by amount."
      #'(lambda (n &optional change-amount)
          (if change-amount
         (setf amount n)
         (+ n amount))))
ENCLOSURE-ADDER
CL-USER> (setf add5 (enclosure-adder 5))
#<FUNCTION :LAMBDA (N &OPTIONAL CHANGE-AMOUNT)
  (IF CHANGE-AMOUNT (SETF AMOUNT N) (+ N AMOUNT))>
CL-USER> (funcall add5 3)
8
CL-USER> (funcall add5 3 t)
3
CL-USER> (funcall add5 3)
6


If you're not sure what is going on with the enclosure, don't worry about it. I can spend some time looking it up. It might be something that you'd want to figure out on your own though.

5. Compose a function [ie from mathematics g compose f(n) === g(f(n))].
Allows you to use functions orthogonally (eg for mapping, eval, etc). Instead of writing a function for a covered call, which is a combination of a written call and owning a stock, I might just compose a function using the written call and stock functions. Useful examples of this appear all the time... unfortunately, I can't think of any at the moment.

Thanks for any help that you might be able to offer.


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Wed Jul 27, 2011 8:58 pm 
8086
8086

Joined: Thu Jul 30, 2009 7:49 am
Posts: 74
1. Any argument may be accessed by its name. Default values can be defined as name=value in the arg list, not sure if this is what you meant by optional, but it can probably be used to implement whatever you did mean. Not sure what you mean by multi-length args, but you can use *name or **name in the function definition to match unmatched arguments(*name puts extra positional arguments from a call in a tuple, **name puts extra keyword arguments in a dictionary).

Code:
>>>def exampleFunction(spam, eggs = 5, *extras, **moreExtras):
...    print(spam, eggs, extras, moreExtras)
...
>>>exampleFunction(1, "two", three = 3)
1 two () {'three': 3}


2. and 4. In python, functions are also objects, that can be passed around at will. to use a function as an object, simply omit the ().
Code:
>>> def run():
...     print("ran")
...
>>> def get():
...     return run
...
>>> get()
<function run at 0x02134FA8>
>>> get()()
ran
>>> def execute(func):
...     func()
...
>>> execute(run)
ran
>>> execute(get())
ran


3. I think I know what you're talking about. Actually, lst*2 does not evaluate to a list with each element *2'ed, instead, it is one list containing the elements of lst twice.
Code:
>>> lst = [1,2,3,4,5]
>>> print(lst*2)
[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

What I think you want are comprehensions.
Code:
>>> print([x*2 for x in [1,2,3]])
[2, 4, 6]
>>> print(lst)
[1, 2, 3, 4, 5]
>>> lst = [x.__str__() for x in lst]#convert each element of lst to a string
>>> print(lst)
['1', '2', '3', '4', '5']

you can use any expression (I think).

I believe that python automatically encloses any variables needed from the local scope at function definition.

I don't quite know what you mean with function composition, an example might help (it doesn't have to do anything useful, just demonstrate the similarity to composite functions in mathematics).


Top
  Profile  
 
 Post subject: Re: Conway's game of life in Python
PostPosted: Fri Jul 29, 2011 1:35 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
I'm a bit distracted with another project at the moment, but I plan on returning to Sage shortly. Thanks for the answers.

freak720 wrote:
1. Any argument may be accessed by its name. Default values can be defined as name=value in the arg list, not sure if this is what you meant by optional, but it can probably be used to implement whatever you did mean.

Pretty much. If an arg has been defined using a name value pair (ie name=value) and I leave the arg out of a function call, it will receive the default value, right?

freak720 wrote:
Not sure what you mean by multi-length args, but you can use *name or **name in the function definition to match unmatched arguments(*name puts extra positional arguments from a call in a tuple, **name puts extra keyword arguments in a dictionary).

No, that isn't what I meant, but that is a very interesting language feature. I'm going to have to think about some uses for it.

What I meant is easily demonstrated using an example. Say I need to write a function to sum integers, but I want it to be able to sum more than two integers because I don't want to have to write code that looks like this...
Code:
(sum 1 (sum 2 3))

... just to sum 1, 2 and 3. Multiple-length args allows me to write the function so that the last argument is basically a list of values and then I can sum (or do whatever) across the list.

freak720 wrote:
2. and 4. In python, functions are also objects, that can be passed around at will. to use a function as an object, simply omit the ().

Nice... I like the get()() example. It is better if you say that functions are "first-class objects" which helps eliminate any confusion with OOP terminology.
freak720 wrote:
3. I think I know what you're talking about. Actually, lst*2 does not evaluate to a list with each element *2'ed, instead, it is one list containing the elements of lst twice.

Yeah, I wrote that and the next day it started bugging me, so I downloaded a new copy of Python for my laptop and saw the same thing. I think that Sage has added some type of list comprehensions to make mathematical operations like the example I gave easier within a limited GUI environment.

freak720 wrote:
I don't quite know what you mean with function composition, an example might help (it doesn't have to do anything useful, just demonstrate the similarity to composite functions in mathematics).

Sure. I should start by saying there is a decent wikipedia article on this subject (w/ an example in Python). One way to think of function composition is the idea of building a function from two or more functions. To keep things simple, we'll combine two functions, but in practice, you tend to get the most bang for you buck when you need to build with more than just two functions. This doesn't really address why you'd want to use composition though. The best answer that I can give is that the ability to compose functions makes a language more orthogonal (in case you don't know what I meant by orthogonal... children's building blocks are highly orthogonal, they work with each other so you can build a wide variety of things with them compared to say the furniture in a room which probably doesn't 'fit together' too well).

Another reason is you can write clearer code by eliminating multiple function calls (eg get()() in Python or (funcall (funcall get)) in Lisp). Now the get()() isn't too bad in your small example, but it would hurt the appearance of your code if you had more function calls (eg get()()()() esp if there are actual args) or if you're using it repeatedly. It tends to be less orthogonal when working with other language features. For example, if I'm using map to apply functions to a list of values, I would have to write a lambda function that calls get()(). OTOH, if I've used a function builder, I could just call the built function which is equivalent of get()(). Another reason for using a function builder is that we might not know which function to use until run-time. I don't necessarily mean this in a polymorphism sense either (ie which method should be called), I mean we might not know which functions until run-time (eg the user defines the function).

Here is fairly simple example. We're going to use print, the built-in timer function, and a sleep function. Let's say that I'm working with some external entity and sometimes I need to add a 1 second delay and other times a 2 second delay between sending messages. We'll say that our messages are sent when I print them. The protocol has "hello", "query" and "end" which take 1s, 2s and 1s, respectively. Let's say that my first script does something like... hello, query1, query2, end. Now the most obvious thing is to write a script like this...
Code:
(defun script ()
  (print 'hello)
  (sleep 1)
  (print 'query)
  (sleep 2)
  (print 'query)
  (sleep 2)
  (print 'end)
  (sleep 1))

Aside from the problem of boring you into a coma, there are some real problems with maintaining something like this script. First, in a longer script, there is a good chance that a typo will mean that you're not delaying the correct amount of time. Second, you can't very well work in an interactive environment in this manner, right? You'd send the command then have to use a stop watch or something... or type out the command (not starting it) and then the delay, then start both of them. Ugh. I don't know about you, but I don't do data entry!

We could write a function that takes a list of commands, iterates through it and does the correct amount of delay. This is a giant improvement, but it doesn't solve the interactive environment problem unless we know exactly everything in advance. It also isn't really orthogonal to the language. We're introducing a new piece of furniture, not something that plays nice with our existing blocks. It also another piece of code for us to maintain and the rather cheesy implementation I've done doesn't scale very well with dozens of additional commands.
Code:
(defun foo (cmds)
  (dolist (cmd cmds)
    (print cmd)
    (if (or (eq x 'hello)
       (eq x 'end))
   (sleep 1)
      (sleep 2))))

I could break this apart and write individual functions like (defun hello () (print 'hello) (sleep 2)), which lets me do something like (hello)(query)(query)(end) and is than even foo, but I'm repeating the same basic code for each command. If there are a hundred commands, I'm still doing data entry, right? And what if some of the commands are more complex, and require additional things like checking for a response? Then both the foo script starts to break down and the individual functions per command becomes even more tedious.

What if we could write a function that built the function for us? Each command would then be a function call. If a command changed, I simply need to rebuild the one function. They're not all intertwined. Plus, I don't need to update any of the scripts because they'd simply be calling the new functions instead. Also, they're now building blocks that play nice with the rest of the language.
Code:
CL-USER> (defun make-cmd (cmd delay)
      #'(lambda ()
          (print cmd)
          (sleep delay)))
MAKE-CMD
CL-USER> (setf hello (make-cmd 'hello 1))
#<FUNCTION :LAMBDA NIL (PRINT CMD) (SLEEP DELAY)>
CL-USER> (setf query (make-cmd 'query 2))
#<FUNCTION :LAMBDA NIL (PRINT CMD) (SLEEP DELAY)>
CL-USER> (setf end (make-cmd 'end 1))
#<FUNCTION :LAMBDA NIL (PRINT CMD) (SLEEP DELAY)>

CL-USER> (defun new-foo (cmds)
      (dolist (cmd cmds) (funcall cmd)))
NEW-FOO
CL-USER> (time (new-foo (list hello query query end)))
HELLO
QUERY
QUERY
END
Real time: 6.005 sec.
Run time: 0.0 sec.
Space: 1352 Bytes
NIL
CL-USER>

Of course, writing a function like new-foo() isn't exactly working with the language orthogonally. What i'd really want to do is use a map instead.
Code:
CL-USER> (time (mapcar #'funcall (list hello query query end)))
HELLO
QUERY
QUERY
END
Real time: 6.006 sec.
Run time: 0.0 sec.
Space: 1376 Bytes
(NIL NIL NIL NIL)
CL-USER>


I think that is a pretty good example of composing functions. Of course, the make-cmd function that I wrote/used isn't very general. A true function builder would allow the user to pass in multiple functions at run-time. I was trying to keep things as simple as possible. One of the best uses of composition is called memoization. In a nutshell, if you have a very time consuming function that makes recursive calls, you can "memoize" repeated function calls. You pass your function to memoize which returns a new function that uses a hash table to store the result (the args are the key, the result the value). Repeated calls with the same key are retrieved from the hash table isntead of being computed. By using composition, you're able to write one memoize function that is able to work with any number of input functions (as opposed to some one off solution for a single function).

Code:
CL-USER> (defun memoize (fn)
      (let ((cache (make-hash-table :test #'equal)))
        #'(lambda (&rest args)
       (multiple-value-bind (val win)
           (gethash args cache)
         (if win
             val
             (setf (gethash args cache) (apply fn args)))))))
MEMOIZE
CL-USER> (defun foo (n)
      "Foo sleeps for n seconds then returns 1 + n."
      (sleep n)
      (1+ n))
FOO
CL-USER> (setf mem-foo (memoize #'foo))
#<FUNCTION :LAMBDA (&REST ARGS)
  (MULTIPLE-VALUE-BIND (VAL WIN) (GETHASH ARGS CACHE)
   (IF WIN VAL (SETF (GETHASH ARGS CACHE) (APPLY FN ARGS))))>
CL-USER> (time (mapcar mem-foo '(1 2 3 4)))   ;;<-- calling the memoized version of foo with four times with 1 2 3 and 4 as input
Real time: 10.0 sec.                                          ;;<-- the amount of time it took due to the sleep function
Run time: 0.0 sec.
Space: 372 Bytes
(2 3 4 5)                                                          ;;<-- the return values
CL-USER> (time (mapcar mem-foo '(1 2 3 4)))
Real time: 0.0 sec.                                            ;;<-- the memoized values are returned here instead
Run time: 0.0 sec.
Space: 64 Bytes
(2 3 4 5)
CL-USER>


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group