An ex post facto law is one that acts retroactively, whether positively or negatively (completely dependent on your point of view). The US Constitution explicitly prohibits them:
No Bill of Attainder or ex post facto Law shall be passed
However, according to Calder v. Bull - 3 U.S. 386 (1798), the definition is slightly narrower than this:
1st. Every law that makes an action done before the passing of the law
and which was innocent when done, criminal and punishes such action.
2nd. Every law that aggravates a crime, or makes it greater than it was
when committed. 3rd. Every law that changes the punishment, and
inflicts a greater punishment than the law annexed to the crime, when
committed. 4th. Every law that alters the legal rules of evidence and
receives less or different testimony than the law required at the time
of the commission of the offense in order to convict the offender
That is to say that you cannot negatively affect a person with a law that retrospectively changes the situation at the time of the offence. This implicitly states that the decriminalisation of an act or lessening of a punishment can be retrospectively applied.
In Hoyt Weaver v. Robert Graham, Governor of Florida. 450 U.S. 24, 101 S.Ct. 960 Justice Marshall referencing Cader v. Bull (among others), decided (my emphasis):
Regardless of whether or not the prospect of gain time was in some
technical sense part of the petitioner's sentence, the statute
substantially alters the consequences attached to a crime already
completed, changing the quantum of punishment, and thus is a
retrospective law which can be constitutionally applied to
petitioner only if it is not to his detriment
An example of a reduction in sentencing is, S. 1789 (111th): Fair Sentencing Act of 2010, which was enacted after a number of attempts by both houses. This amended a number of previous acts to reduce the disparity in sentencing for those found in possession of crack cocaine as opposed to powder cocaine. This did not reduce the sentence of those already imprisoned under the amended acts.
The crucial point is that any act, which reduced the sentencing for, say, possession of marijuana would have to explicitly state that it is being applied retroactively in order to automatically release people from prison (a physical and administrative act that, itself, may take a while). An act could also offer guidance to parole boards that releasing a prisoner is the preferred method, allowing the release of prisoners to gradually filter through. I can't find any examples of this actually happening in the US, though I'm sure it has.
Europe has an, almost identical, definition. The European Convention on Human Rights (ECHR), in Article 7 states:
- No one shall be held guilty of any criminal offence on account of any act or omission which did not constitute a criminal offence under
national or international law at the time when it was committed. Nor
shall a heavier penalty be imposed than the one that was applicable at
the time the criminal offence was committed.
- This article shall not prejudice the trial and punishment of any person for any act or omission which, at the time when it was
committed, was criminal according to the general principles of law
recognised by civilised nations.
Don't forget that the ECHR applies to all members of the Council of Europe, not just the EU. Though, the Treaty of Lisbon contained a protocol allowing for the accession of the EU to the Council:
arrangements for the Union's possible participation in the control bodies of the European Convention;
One of the more notable, retrospective, criminal Acts in the UK is the War Crimes Act 1991, which allowed for the punishment, by British Courts, of people responsible for war crimes during WWII, i.e. before the Geneva Conventions. This would, theoretically, have been in breach of the ECHR.