[fpc-other] PROLOG written in Pascal

[Marco van de Voort]

In our previous episode, Mark Morgan Lloyd said:
> > I don't understand why interested people couldn't implement mark/release for
> > the base TP compatible level of FPC ?  What is so different between TP and
> > FPC there?
> > 
> > Of course it wouldn't scale, but TP didn't scale further than 16MB anyway
> > (64MB with 386 tricks).
> > 
> > Basically you only need an own heapmanager that allocates all allocations
> > in-order from a 16MB block, and mark and release procedures that call that
> > heapmanager and are declared in some unit preloaded wiht -Fa?
> 
> The main issue is that dynamic memory is used by the Prolog 
> implementation in several different ways. The first way is that as rules 
> are being entered, they go into memory and usually stay there. The 
> second way is that as queries are evaluated a lot of temporary stuff 
> (variable bindings etc.) is put into memory, this is all thrown away on 
> completion. The third way is that during query evaluation, rules could 
> potentially be added/deleted/changed which shouldn't be thrown away.

How does this work in TP? Mark/release would remove all variables, not just
the temprary ones. Or are the persistent and temporary orders not mixed, and
is only the temporary part under mark/release?

> I think that in practice this could be handled by normal OO techniques, 
> since these days the amount of (virtual) memory is significantly larger 
> than typical embedded problems. If somebody wanted to e.g. process the 
> entire collection of Wikipedia titles and categories as a set of rules 
> then they should probably be using specialist tools.

(in case it wasn't clear, the problem is that mark/release either requires
memory to be available as one contageous block.  There is no guarantee that
an existing block can be expanded later, so you need to allocate it up front
(the 16MB above).  

To work around it, in theory one could allocate a new heap on every mark (if free mem< a
certain threshold), and maintain a linked list of blocks that are scanned
through for mark/release operations, but that is (1) costly, so you would
need to pace your mark/releases (2) you still need an upper limit.
 
If address space is large enough (read: 64-bit) you might only reserve
relatively large blocks, regardless of much you use.

> >> I was reminded of this by the discussion elsewhere on refcounted 
> >> objects, which would obviously be another way to do it. Timothy Budd's 
> >> book on Leda gives an interesting example of using the unification 
> >> operation which underpins Prolog to process graph structures.
> > 
> > Prolog is an interpreter, and I assume its structures are movable. Native
> > languages allocations usually aren't.
> 
> Up to a point. A typical Prolog implementation acts as an interpreter 
> since rules and queries are entered interactively, however the 
> underlying unification algorithm can equally well be embedded in 
> compiled code

My point is more that if the prolog interpreter can move its allocations so
that the program remains working

IOW if I do

mark
  new(persist);
  new (temp);
<---
release

can I run a routine at the <--- point that moves all persistent allocations
from the block of mark..release to a new or existing,  persistent heap?

Does it keep track of what is temp and what is persistent?