If you were to make a program to analyze a program for the same platform with the same limits as the analyzing programs it's impossible for such analyzer to exist. This is known as the halting problem.
When that said, halting problem is solvable for programs that has a lot less memory consumption and code length than the analyzing program can have. Eg. I can make a halt? procedure for all 2 byte BrainFuck-programs like this:
;; takes a valid 2 byte BF-program
;; and returns if it will halt
(define (halt? x)
(cond ((equal? x "[]") #f)
(else #t)))
A larger example is by making an interpreter and hash memory states and pc-location. If a previous state is found it's an infinite loop. Even with a very good data model the memory used by the interpreter must be considerable larger than what it interprets.
I'm thinking of constant folding programs by doing and the halting problem becomes an issue. My idea is to have a data structure that has the number of times a particular branch in AST has been seen and have a cutoff limit that is very large. Thus if the interpreter has been at a branch more than the cutoff it will end up in the compiled program instead of it's computation. It takes a lot less memory and will establish that some or all parts of a program certainly does return (halt).
Imagine this code:
(define (make-list n f)
(if (zero? n)
'()
(cons (f) (make-list (- n 1) f))))
(define (a)
(b))
(define (b)
(c))
(define (c)
(b))
(display (make-list 4 read))
(display (make-list 4 a))
It's actually pretty bad code since you don't know which order the input might get. The compiler get to choose whats best and it might turn into:
(display-const "(")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const ")")
(display (cons (b) (cons (b) (cons (b) (cons (b) '())))) ; gave up on (b)