Is there a criteria in Smart Lists that can show me anyone who has been part of specific program in the past, but isn't currently? Since many programs use Smart Lists and people may fall off the Smart Lists with a value change, they would no longer be a member.
I assume from the statement you create under Member of Program that it is show those currently in the program. And the constraints are aquired by, program status, success.
Take a look at Marketo's documentation around program membership - Understanding Program Membership - Marketo Docs - Product Documentation. Membership within a program is not based on membership within smart lists - it's based typically more on static list imports, form fill outs, and most critically on program statuses. So, for example, if someone was in a program due to their inclusion in a smart list, and had their program status set, then they'll still be a member of that program even if they're no longer a member of that list.
Hope that helps.
Like Grace said, program membership is attributed to having a program status, not simply being a member of a smart list.
However, if the individuals were in fact members of the program but were removed from the program, drag in the Program Status was Changed Filter. Select your program and then add New Status and Old Status from Add Constraint. New Status is "Not in Program". Old Status is any (minus not in program). I'm pretty sure that will pull in people who were once members and no longer are.
Hope this helps!