Other Programming Languages
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming Languages - MoreOther Programming Languages

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old January 21st, 2013, 12:17 AM
zemon1 zemon1 is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2008
Posts: 76 zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level)zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level)zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level)zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level)zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level)zemon1 User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 1 Day 4 h 40 m 16 sec
Reputation Power: 25
[LISP] Keep having a stack overflow

Hello,
In the code below I keep getting a stack overflow. To run this code enter "(runGA 100)". I feel like the issue is with getChromo, because even if I don't call chromoParens sometimes it overflows. With chromoParens it ALWAYS overflows though so i have a good feeling there is definitely a problem in there. I just cant seem to find them.

Thanks for looking.

Code:
(defconstant CHROMOSIZE 10)
(defconstant POPSIZE 5)

(defvar OpArgCount 
    '((* 2) (/ 2) (+ 2) (- 2) (expt 2) (sqrt 1) (% 2) (floor 1) (round 1) (ceiling 1) (isqrt 1) (abs 1)))

(defvar possibleOps 
    '(* / + - expt sqrt % floor round ceiling isqrt abs))

(defvar possibleNums
    '(1 2 3 4 5 6 7 8 9 .1 .2 .3 .4 .5 .6 .7 .8 .9))

(defvar allItems 
    (append possibleOps possibleNums))

;Done
(defun randomItem ()
    (list (elt allItems (random (length allItems))))
)

(defun runGA (goal)
    ;(printPop (fitnessPop (createPop POPSIZE ()) nil goal))
    ;(printPop (fitnessPop (createPop POPSIZE ()) nil goal))
    (chromoParens (createPop POPSIZE ()) nil) 
)

;Done
(defun createPerson (id chromosome)
    "Creates a single person"
    (if (equal chromosome nil)
        ;Call a random chromo function
        
        ;(getChromo '(1 2 3 / 5) -1 ())
        (let ((res (randomChromo CHROMOSIZE ()))) 
            ;(print res)
            ;(print (countOps res 0))
        ;    (getChromo res -1 ())
            res
        )
        ;(randomChromo CHROMOSIZE ())
        chromosome
    )     
)

;Done
(defun createPop (thePop people)
    "Creates the original population"
    (if (equal 0 thePop)
        people
        (createPop (- thePop 1) (push (createPerson thePop nil) people))
    )
)

;Done
(defun randomChromo (size chromo)
    (if (equal 0 size)
        chromo
        (randomChromo (- size 1) (append chromo (randomItem)))
    )    
)

;Done
(defun getChromo (chromo opReq result)
    "Explanation"
    (let ((op (first chromo)))
 
        ;If base return
        (if (equal 0 opReq)
            result
            ;If gene is an operation add to requirement ect
            (if (member op possibleOps)
                ;Is this my first run? if so get rid of that -1
                (if (equal -1 opReq)  
                    (getChromo 
                        (cdr chromo) 
                        (+ opReq (second (assoc op opArgCount)) 1) 
                        (append result (list op))
                    )
                    (getChromo 
                        (cdr chromo) 
                        (+ opReq (second (assoc op opArgCount))) 
                        (append result (list op))
                    )
                )
                ;If not, its a number so are we in an expression?
                (if (> opReq 0)
                    ;We are, so reduce the required numbers and add it to the result list
                    (getChromo 
                        (cdr chromo)
                        (- opReq 1) 
                        (append result (list op))
                    )
                    ;We aren't and we need to be so keep looking for an op
                    (getChromo 
                        (cdr chromo)
                        -1 
                        result
                    )
                )
            )
        )
    )
)

;Done
(defun countOps (chromo result)
    "Counts the number of operators in the chromo"
    (
    let ((front (first chromo)))
        (if (equal chromo nil)
            result
            (if (member front possibleOps)
                (countOps (cdr chromo) (+ result 1))
                (countOps (cdr chromo) result)
            )
        )
    )
)

(defun fitnessPerson (goal person)
    ""
    (let ((opChromo (getChromo person -1 ())))
        ;(print opChromo)
        (if (member nil person)
            ;If there is a nil in it's formula make it an exteremly bad mate
            (list person 1000000000 750000)
            ;(list person (- goal (eval opChromo)) (countOps opChromo 0))
            (list person opChromo (countOps opChromo 0))
        )
    )
)

(defun fitnessPop (people res goal)
    (if (equal people nil)
        res
        (fitnessPop (cdr people) (append res (fitnessPerson goal (first people))) goal)
    )    
)

(defun chromoParens (people res)
    "Explain"
    (print (first people))
    (if (equal people nil)
        res
        (chromoParens (cdr people) (append res (getChromo (list (car people)) -1 ())))
    )
)

;Need to add parens to expressions
(defun printPop (people)
    "Prints ever population member seperated by new lines"
    (print (first people))
    ;(format t "~%")
    (if (equal nil people)
        nil
        (printPop (cdr people))
    )
)

Reply With Quote
  #2  
Old January 22nd, 2013, 09:00 PM
OmegaZero OmegaZero is offline
Contributing User
Dev Shed Novice (500 - 999 posts)
 
Join Date: May 2007
Posts: 737 OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level)OmegaZero User rank is General (90000 - 100000 Reputation Level) 
Time spent in forums: 3 Weeks 4 Days 22 h 50 m 49 sec
Reputation Power: 928
Have you done any unit testing? If you construct a simple input (one simple enough that you can compute the proper result by hand) and pass it to the functions you're suspicious of do you get the right results back?

Most interpreters can give you stack trace that would let you track down where the infinite sequence of calls is. Have you looked at the options for your lisp interpreter? If your interpreter doesn't have this option, you can get similar information by placing a print expression at the start of each function to write out the function's name and arguments.

Naive implementations using Lisp are prone to stack overflows by the nature of recursion. At first glance it looks like all of your functions are safely tail-recursive, but it would be worth trying smaller values in your program to see what happens.
__________________
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming Languages - MoreOther Programming Languages > [LISP] Keep having a stack overflow

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap