WAM Free Variables?

Appeared in Volume 7/3, August 1994

Keywords: WAM.


eep2pc@ee.surrey.ac.uk 
Paul Connolly
6th March 1994

Free variables are represented in the WAM as a pair consisting of a tag = REF and a value = address of the word holding the free variable (ie a self referential pointer). I would like to ask why this format was chosen?

Doesn't this complicate dereferencing because when a REF cell is found then a check of the value must be made to determine whether the dereferencing should continue (or if a free variable has been found at the end of the chain)?

If the two bit tag REF were coded as binary 11 and the free value represented by all 0's then only a single comparison need be made in each iteration of dereferencing to check whether the end of the chain has been reached.


noye@irisa.fr 
Jacques Noye
9th March 1994

It may be that introducing a tag 'free' can speed up the main loop of dereferencing, but this is not what matters. It turns out that most dereference chains are very short. For instance, Touati and Despain have shown in [1] that most chains are typically of length 0 and that there is almost no chain of length > 1. Also, when the length is 1, the case non variable is more frequent than the case free variable.

[1] H. Touati and A. Despain, An Empirical Study of the Warren Abstract Machine, Proceedings of the 1987 Symposium on Logic Programming, San Francisco, August/September 1987, IEEE Computer Society Press.

PS: The story may be different in a scheme where unbound variables are allowed to reside in argument registers.


andi@mips.complang.tuwien.ac.at 
Andi Krall
8th March 1994

Paul Connolly writes:

I would like to ask why this format was chosen?

The self referential pointer enables the assignment of free variables to WAM registers without checking the tag. It simplifies the code for some instructions.


joachim@ecrc.de 
Joachim Schimpf
7th March 1994

Paul Connolly writes:

I would like to ask why this format was chosen?

The advantage is that you can copy a word without looking at its contents. I.e. copying a free variable automatically creates a reference to the free variable (rather than a new free variable).

However, there have been Prolog systems with separate REF and FREE tags.