Problems implementing some basic machine instructions for a WAM based Prolog

Help!
1

Hello fellow prologgers,

I’ve been trying to implement a WAM-based Prolog for fun and just out of pure curiosity. I’ve been following the famous WAM Tutorial reconstruction and I am really stuck/confused on Exercise 2.3. In other words:

Verify that the effect of executing the sequence of instructions shown in Figure 2.4 right after that in Figure 2.3 produces the MGU of the terms p(Z, h(Z, W), f(W)) and p(f(X), h(Y, f(a)), Y) . That is, the (dereferenced) bindings corresponding to W = f(a) , X = f(a) , Y = f(f(a)) , Z = f(f(a)) .

I have a unit-test that executes these machine instructions at line 712.

The log-output of my heap-cell representation looks like this:

[DEBUG bfg_prolog::tests] [Str(1), Func(Functor(“h”, 2)), Str(13), Str(16), Str(5), Func(Functor(“f”, 1)), Ref(3), Str(8), Func(Functor(“p”, 3)), Ref(2), Str(1), Str(5), Str(13), Func(Functor(“f”, 1)), Ref(14), Str(16), Func(Functor(“f”, 1)), Str(19), Str(19), Func(Functor(“a”, 0))]

Here’s my x-register:

[DEBUG bfg_prolog::tests] [1: Str(8), 2: Ref(2), 3: Str(1), 4: Str(5), 5: Ref(14), 6: Ref(3), 7: Ref(17)]

For the most part my heap-cell state seems to agree with the exercises’s expected output, with one crucial difference: observe the cell at address 14, i.e. Ref(14). It’s a self-referential cell, in other words, an unbound variable. The way I see it, it should not be Ref(14), but should actually be Ref(3) on the heap, which would effectively resolve Str(13) to f(f(a)). I’ve been banging my head against this problem for several days and I can’t really see what I’m doing wrong with the implementation of my instructions, deref, bind function, etc.

Can any of the WAM/compiler gurus give me any insight as to what might be going on here? I decided to implement this in Rust (FWIW, it looks really similar to other languages in the C family, so it shouldn’t be too hard to figure out what’s going on), so I apologize if this causes difficulty. Let me know if you’d like some additional information, debug-output, etc. Any tips/advice would be greatly appreciated.

Thanks in Advance,
Ebrahim Azarisooreh

2

Hi,

Are you the eazar001 maintaining swi-prolog-devel for archlinux? It has been out of date for a little bit, if so, could you update it? Thanks!

(sorry I can’t help with the WAM problem you are having)

3

Hi, yes that’s me. I actually disowned that package because I rarely use Arch Linux these days. You are free to pick up maintaining that package however. Sorry for the troubles.

4

Don’t know an answer to your question but it seems others have walked the path you are walking.

See: Scryer Prolog

Produce an implementation of the Warren Abstract Machine in Rust, done according to the progression of languages in Warren’s Abstract Machine: A Tutorial Reconstruction.

1 Like
5

Rereading some of the literature I quickly remember why I haven’t implemented the WAM, as noted the paper is lacking details that would make implementing a WAM straight forward. The tutorial paper tries to bridge the gaps and seems to be of use because others are making use of it and seem to be successful; I say seem because I have not tried to verify their version.

So it seems your problem, like many problems, is that you are on one side of a large canyon looking to get to the other side and you see a bridge, the problem is the bridge was made for giants who can take steps spanning 10 ft and you can only take steps of 2 ft. Then you find a paper that has boards the can span the 10 ft gaps but sadly they have holes in them and so only a person who can step 4 ft can use the boards. My suggestion is to find more papers that can fill in those gaps so that those 4 ft gaps become 2 ft. :smiley:

If you have been following along with some of my topics and replies you will see that I am working on implementing PostScript in Prolog which has some parallels to what you are doing, e.g. implementing a stack based VM. How I bridge the gaps is to use a bottom up design approach, make lots of test cases and am not afraid to throw out every line of code and start over if it is wrong. (That should be one of the golden rules of programming). I also like to make pictures, keep lots of references to documents and keep detailed comments in the code.

Also don’t forget to check the slides and errata.

6

Thanks for the advice! Yes, I’ve seen bits of scryer-prolog, and was actually surprised how similar our (corresponding) implementations turned out to be, which is why I’m stumped as to why I can’t pass this one bit of verification. However, perhaps you’re right. I may need to examine a few research papers; I know Paul Tarau has a lot of interesting insight into not only the WAM, but innovations on top of it as well. I have not seen the slides and errata, so I’ll be sure to check them out.

1 Like
7

Also, I know this is a bit late, but just in case anybody would like more information as to what’s going on, I’m providing a full trace of the actions of my code below.

 put_structure: 
 		HEAP[0] <- Str(1)
 		HEAP[1] <- Functor(h/2)
 		X3 <- Str(1)
 		H <- H + 2
 set_variable: 
 		HEAP[2] <- Ref(2)
 		X2 <- Ref(2)
 		H <- H + 1
 set_variable: 
 		HEAP[3] <- Ref(3)
 		X5 <- Ref(3)
 		H <- H + 1
 put_structure: 
 		HEAP[4] <- Str(5)
 		HEAP[5] <- Functor(f/1)
 		X4 <- Str(5)
 		H <- H + 2
 set_value: 
 		HEAP[6] <- Ref(3)
 		H <- H + 1
 put_structure: 
 		HEAP[7] <- Str(8)
 		HEAP[8] <- Functor(p/3)
 		X1 <- Str(8)
 		H <- H + 2
 set_value: 
 		HEAP[9] <- Ref(2)
 		H <- H + 1
 set_value: 
 		HEAP[10] <- Str(1)
 		H <- H + 1
 set_value: 
 		HEAP[11] <- Str(5)
 		H <- H + 1
 get_structure: 
 		deref: XAddr(1) -> XAddr(1)
 		S <- 9
 		Mode <- Read
 unify_variable (Read): 
 		X2 <- Ref(2)
 		S <- S + 1
 unify_variable (Read): 
 		X3 <- Str(1)
 		S <- S + 1
 unify_variable (Read): 
 		X4 <- Str(5)
 		S <- S + 1
 get_structure: 
 		deref: XAddr(2) -> XAddr(2)
 		HEAP[12] <- Str(13)
 		HEAP[13] <- Functor(f/1)
 		bind: HEAP[2] <- Str(13) | (Ref(2) -> Str(13))
 		H <- H + 2
 		Mode <- Write
 unify_variable (Write): 
 		HEAP[14] <- Ref(14)
 		X5 <- Ref(14)
 		H <- H + 1
 		S <- S + 1
 get_structure: 
 		deref: XAddr(3) -> XAddr(3)
 		S <- 2
 		Mode <- Read
 unify_value (Read): 
 		unify: XAddr(4) <-> HeapAddr(2)
 		Fail <- false
 		deref: HeapAddr(2) -> HeapAddr(2)
 		deref: XAddr(4) -> XAddr(4)
 		get_functor: Str(13) -> f/1
 		get_functor: Str(5) -> f/1
 		S <- S + 1
 unify_variable (Read): 
 		X6 <- Ref(3)
 		S <- S + 1
 get_structure: 
 		deref: XAddr(6) -> HeapAddr(3)
 		HEAP[15] <- Str(16)
 		HEAP[16] <- Functor(f/1)
 		bind: HEAP[3] <- Str(16) | (Ref(3) -> Str(16))
 		H <- H + 2
 		Mode <- Write
 unify_variable (Write): 
 		HEAP[17] <- Ref(17)
 		X7 <- Ref(17)
 		H <- H + 1
 		S <- S + 1
 get_structure: 
 		deref: XAddr(7) -> HeapAddr(17)
 		HEAP[18] <- Str(19)
 		HEAP[19] <- Functor(a/0)
 		bind: HEAP[17] <- Str(19) | (Ref(17) -> Str(19))
 		H <- H + 2
 		Mode <- Write
		
		
[Str(1), Func(Functor("h", 2)), Str(13), Str(16), Str(5), Func(Functor("f", 1)), Ref(3), Str(8), Func(Functor("p", 3)), Ref(2), Str(1), Str(5), Str(13), Func(Functor("f", 1)), Ref(14), Str(16), Func(Functor("f", 1)), Str(19), Str(19), Func(Functor("a", 0))]
[1: Str(8), 2: Ref(2), 3: Str(1), 4: Str(5), 5: Ref(14), 6: Ref(3), 7: Ref(17)]
true.
8

So … I actually feel really silly. I found the error that was causing me days of headaches. See the diff here.

It turns out that when I was popping structure args from the push-down list I wasn’t doing it (inclusively) to n, but exclusively. Either way, the problem is solved, and now I can move on to the later stages like choice points, backtracking, etc.

I do thank you for the advice/support/help however.

9

Awesome, :clap: I know the feeling and those types of mistakes.

Don’t forget to make a unit test; I know you know that, but when someone gives you a nudge you feel better doing it.

10

Oh, I’ll ante up on that unit-test, I’ll add some debug trace statements in there too! Also yes, “nudges” do give you a good motivation-shot.

11

Don’t know exactly what you mean by that.
I know what debug is and trace statements are, but this sounds like you are triggering them in the code; just-in-time debugging. That I have never done with SWI-Prolog.

I typically use assertion/1 (not to be confused with assert/1) and is_of_type/2.

Just for the record, in just my PostScript scanner there are over 8,000 unit test. In doing them found out that +. is a valid PostScript name. :smiley:

12

Since you are creating test cases, just the other day Jan listed a unification case that I have not seen before.

?- X=f(X), Y=f(Y), X=Y.
X=Y, Y=f(Y).

and the explanation in the code.

Would be interesting to see if your WAM can do it.

13

Think Log4J. Basically, you have printed output, that you can assign levels of logging during your program’s runtime. Your levels are info, warning, error, debug, and trace. Depending on the level you set (i.e. in production vs. development), some messages will be suppressed, and others will go through. You can even hook on certain log messages to make them format/behave differently. Also yes, message-logging/hooking does exist in SWI Prolog as well as Logtalk. The facilities are excellent in this regard.

It’s really good when you want to trace your code at a deeper level, but don’t really want to fire up GDB.

14

Yes, you’re referring to cyclic terms, which is a feature supported by SWI-Prolog, but not necessarily others. GNU and XSB don’t support that, for example. I may consider looking into it, but I’m unsure of the ramifications of implementing it in my system.

15

Are you using Log4P or something else? I played with this once, but my never had a need to spin it up for a real project.

16

Remember, I’m implementing my interpreter in Rust, so I don’t have Prolog facilities for debugging. I’m basically using a Rust analogue of a Java (Log4J) tool/framework.

p.s. I hate Java

17

Ahh, yes. Thanks for the reminder.

Me too. It is one of those languages I use only when I have too, but for Neo4j embedded I have little choice.