Just introduce a syntax to define immutable variables (e.g. like "val" in Scala) and to mark particular functions as pure (easy to implement manually as a decorator in Python, I've been using it a lot) and memoization becomes a seemingly easy task. Why a new language?
By the way it seems very sad to me that the majority of imperative and hybrid (functional×imperative) languages lack syntax for immutable variables: in just so many cases I introduce a variable to store an intermediate result of an operation an don't mean to re-assign it ever after, it's nice of a developer to define this intention explicitly and of a compiler to raise an error when the variable is re-assigned accidentally - this simple feature is among the reasons why Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully.
By the way it seems very sad to me that the majority of imperative and hybrid (functional×imperative) languages lack syntax for immutable variables: in just so many cases I introduce a variable to store an intermediate result of an operation an don't mean to re-assign it ever after, it's nice of a developer to define this intention explicitly and of a compiler to raise an error when the variable is re-assigned accidentally - this simple feature is among the reasons why Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully.