Lambda the Ultimate

This is something I have been wondering about recently..

The basic idea is memoized data that decays over time.

• The first time data is required it is calculated
• If it took substantial time to calculate it is memoized and calculation time recorded
• Subsequent requests to the data (with same parameters) are given the memoized version
• The memoized data decays over time based on a metric that incorporates data size, calculation time, last access time, current memory load and so forth
• Once the memoized data has fully decayed, it is freed from memory
• Future requests to the data cause it to be recalculated, and (re)memoized
• Repeat

At first glance, this seems like it might give a nice dynamic time/space balance to certain aspects of a programming language.

Having not come across the idea before, I was wondering if anyone might point me towards any languages or papers on the subject?

Hi,
I'm studying the lambda calculus and there's something I can't understand in the fixed point theorem.

I'm reading the Barendregt book Lamba Calculi with Types, but at the moment I'm studyng the untyped one, in the first part of the book.

It says there is a fixed point combinator: ( \ = lambda )

Y = \f.(\x.f(xx))(\x.f(xx))

such that

for any F, F(YF) = YF

So, if my F is just a variable, let's say F = q, then how

q(Yq) can become Yq?

I am sure I am missing something.
Can you help me?

Thanks,
Carlo

Certain rules are considered "unsafe" and disallowed in Datalog because they don't restrict all of their variables to a finite domain (and therefore may not have a finite number of solutions). For instance, in:

beef(X) :- lemur(X), not(alice(X, Y)), not(bahnanlagen(Y)).

Y is not restricted to a finite domain, so the rule is unsafe. Additionally, no use of the beef predicate can further restrict the domain of Y. However, a rule may be unsafe only because its distinguished variables are not restricted:

orange(X) :- zorro(Y), X < Y.

A predicate like orange/1 doesn't seem different from a negated relational predicate or an arithmetic predicate, since its otherwise unrestricted variables can be further restricted by the context in which it is used. For instance, a rule like:

fromage(X) :- elephant(X), orange(X).

...appears to be safe (where elephant/1 and zorro/1 are safe relational predicates). After all, the apparently equivalent:

fromage(X) :- elephant(X), zorro(Y), X < Y.

...is safe in that case. Provided their use is restricted in the same fashion as negated and arithmetic predicates, are there any problems with permitting this latter kind of unsafe rule that I'm just not seeing?