Converting to dot notation in prolog

Question

I have to represent [[fruits],[ ] ] in dot notation form in Prolog, and below is how I did it ,but something tells me this is wrong because I have expanded [[ ]] too, is this incorrect ?

.([fruits],[[ ]] )

.(.(fruits, []),.([],[])

Answer 1

Originally in prolog there was no [] and the vector was always constructed using the . .

Here is an example from a 1979y paper by David Warren [*36'footnote] :

  ([user]) .

  :- (op(1,'xfy','.')) .

  concatenated(nil,L,L) . 
  concatenated((X.L1),L2,(X.L3)) :- concatenated(L1,L2,L3) .

  %^D

testing and demonstration ...

  /*
  ((concatenated((nil),(nil),Z)) , Z == (nil)) .
  ((concatenated((a.b.nil),(c.d.nil),Z)) , Z == (a.b.c.d.nil)) .
  */

  ?- ((concatenated((nil),(nil),Z)) , Z == (nil)) .
  %@ Z = nil
  ?- ((concatenated((a.b.nil),(c.d.nil),Z)) , Z == (a.b.c.d.nil)) .
  %@ Z = [a,b,c,d|nil]

The above works in yap , eclipse , gprolog , xsb. However it does not work in swipl (see appendix).

concatenated as presented in the paper is exactly the same as the typical-modern-day prolog implementation of append, but with a different name , and a different marker for the end.

The general pattern is that each element is separated from it's neighbour via the ..

The last element is a marker to indicate the end. In Warren's example nil is the marker that indicates the end. The use of nil seems to have been a convention but not a requirement. Subsequent developments in prolog replaced the use of nil as the marker for the end with the use of [] as the marker for the end.

Warren's seminal example can be minimally rewritten to use [] instead of nil...

  ([user]) .

  ((append([] , L , L))) . 

  (
     (append((X.L1) , L2 , (X.L3))) 
  )
  :- 
  (
     (append(L1 , L2 , L3)) 
  )
  .

  %^D

  /*
  ((append(([]) , ([]) , Z)) , (Z == [])) .
  ((append((a.b.[]),(c.d.[]),Z)) , Z == (a.b.c.d.[])) .
  ((append((a.b.[]),(c.d.[]),Z)) , Z == [a,b,c,d]) .
  ((append(([a,b]),([c,d]),Z)) , Z == [a,b,c,d]) .
  */

  ?- ((append(([]) , ([]) , Z)) , (Z == [])) .
  %@ Z = []
  ?- ((append((a.b.[]),(c.d.[]),Z)) , Z == (a.b.c.d.[])) .
  %@ Z = [a,b,c,d]
  ?- ((append((a.b.[]),(c.d.[]),Z)) , Z == [a,b,c,d]) .
  %@ Z = [a,b,c,d]
  ?- ((append(([a,b]),([c,d]),Z)) , Z == [a,b,c,d]) .
  %@ Z = [a,b,c,d]

Warren continues ...

... where a list is either the atom 'nil' or a term formed from the binary functor '.' whose second argument is a list ... we write the functor as a right-associative infix operator so that , for example , the first list mentioned [ed: (a.b.c.d.nil)] is equivalent to the standard form .(a,.(b,.(c,.(d,nil))))'

Warren provides this example ...

  ([user]) .

  list(nil) . 

  list(.(X,L)) :- list(L) .

  %^D

testing and demonstration ...

  /*
  ((List = (nil)) , (list(List))) .
  (\+ ((List = (a)) ,  (list(List)))) .
  ((List = (a.nil)) , (list(List))) .
  (\+ ((List = (nil.a)) , (list(List)))) .
  ((List = (nil.nil)) , (list(List))) .
  */

  ?- ((List = (nil)) , (list(List))) .
  %@ List = nil
  ?- (\+ ((List = (a)) ,  (list(List)))) .
  %@ true
  ?- ((List = (a.nil)) , (list(List))) .
  %@ List = [a|nil]
  ?- (\+ ((List = (nil.a)) , (list(List)))) .
  %@ true
  ?- ((List = (nil.nil)) , (list(List))) .
  %@ List = [nil|nil]

That implementation of (list(L)) , now 40 years ago , does not meet the modern expectations of a "logic" program ...

  % does it provide a useful answer in the general case ?

  ?- ((List = _) , (list(List))) .
  %@ List = nil ? ;
  %@ List = [_A|nil] ? ;
  %@ List = [_A,_B|nil] ? ;
  %@ List = [_A,_B,_C|nil] ? ;
  %@ List = [_A,_B,_C,_D|nil] ? ;
  %@ !! etc ... non-terminating !!
  %@ ^CAction (h for help): a

  % is it steadfast ?

  ?- ((list(List)) , (List = (nil))) .
  %@ List = nil ? ;
  %@ !! hang , non-terminating !!
  %@ ^CAction (h for help): a

... I don't know how to fix those problems .

When Warren writes ...

we write the functor as a right-associative infix operator so that ...

... I think he is referring to this peculiar and useful feature of the prolog xfy ...

  ([user]) .

  :- ((op(10'1,'xfy','~'))) .

  %^D

  /*
  (((Left ~ Rest) = (a ~ b ~ c ~ d ~ e)) , (Left == a) , (Rest == (b~c~d~e))) .
  (((Left_1 ~ Left_2 ~ Rest) = (a ~ b ~ c ~ d ~ e)) , (Left_1 == a) , (Left_2 == b) , (Rest == (c ~ d ~ e))) .
  */

  ?- (((Left ~ Rest) = (a ~ b ~ c ~ d ~ e)) , (Left == a) , (Rest == (b~c~d~e))) .
  %@ Left = a,
  %@ Rest = b~c~d~e
  ?- (((Left_1 ~ Left_2 ~ Rest) = (a ~ b ~ c ~ d ~ e)) , (Left_1 == a) , (Left_2 == b) , (Rest == (c ~ d ~ e))) .
  %@ Left_1 = a,
  %@ Left_2 = b,
  %@ Rest = c~d~e

It is reasonable to expect the yfx operator to behave in reverse ; whereas xfy allows you to grab elements from the left and ignore the rest to the right , perhaps yfx allows you to grab elements from the right and ignore the rest to the left ...

  :- ((op(10'1,'yfx','~'))) .

  %^D

  /*
  (((Rest ~ Right) = (a ~ b ~ c ~ d ~ e)) , (Rest == a~b~c~d) , (Right == e)) .
  (((Rest ~ Right_2 ~ Right_1) = (a ~ b ~ c ~ d ~ e)) ,  (Rest == a ~ b ~ c) , (Right_2 == d) , (Right_1 == e)) .
  */

  ?- (((Rest ~ Right) = (a ~ b ~ c ~ d ~ e)) , (Rest == a~b~c~d) , (Right == e)) .
  %@ Rest = a~b~c~d,
  %@ Right = e
  ?- (((Rest ~ Right_2 ~ Right_1) = (a ~ b ~ c ~ d ~ e)) ,  (Rest == a ~ b ~ c) , (Right_2 == d) , (Right_1 == e)) .
  %@ Rest = a~b~c,
  %@ Right_1 = e,
  %@ Right_2 = d

[*36'footnote] --- https://www.era.lib.ed.ac.uk/bitstream/handle/1842/6648/Warren1978.pdf

appendix

Don't bother to try playing with . or [] in swipl , neither the . nor the [] are functional as described .

I reported a bug to swipl about .; assuming non-conformance to traditional and standard prolog systems was of interest; it appears that it is not.

https://github.com/SWI-Prolog/issues/issues/55

The author of swipl makes the suggestion of using term_expansion, however neither the use of term_expansion nor goal_expansion can fix the following basic compatibility issues.

  /*
  (a.b.[]) =[a,b]  .
  A ={ foo:a.b.nil } .
  [a,b|[c,d]] = [a,b,..[c,d]] .
  */

  $ yap
  + yap
  YAP 6.2.2 (x86_64-linux): Wed Sep  7 07:48:47 PDT 2016
  MYDDAS version MYDDAS-0.9.1
     ?- (a.b.[]) =[a,b]  .
     %@ yes
     ?- A ={ foo:a.b.nil } .
     %@ A = {[foo:a,b|nil]}
     ?- [a,b|[c,d]] = [a,b,..[c,d]] .
     %@ yes
     ?- (halt) .
  % YAP execution halted

  $ swipl
  + swipl
  Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.27)
  Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam
  SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is LGPL free software,
  and you are welcome to redistribute it under certain conditions.

  For help, use ?- help(Topic). or ?- apropos(Word).

  ?- (a.b.[]) =[a,b]  .
  ERROR: Type error: `dict' expected, found `a' (an atom)
  ?- A ={ foo:a.b.nil } .
  ERROR: Type error: `dict' expected, found `a' (an atom)
  ?- [a,b|[c,d]] = [a,b,..[c,d]] .
  ERROR: Syntax error: Operator expected
  ERROR: [a,b|[c,d]] = [a,b,.
  ERROR: ** here **
  ERROR: .[c,d]] . 
  ?- (end_of_file) .

  % halt

... suggesting to me that perhaps the author of swipl does not know prolog very well (term_expansion?!??!) or is not interested in prolog conformance or is interested in establishing vendor lock-in .

Answer 2

Well, the ./2 is what is in Lisp known as the cons. It contains two parameters: a head the element, and a tail. The tail can be the empty list [], or another cons.

Let us first look at the term we have to convert:

X = [ [fruits] , [] ]

What we see is an outer list with two elements (we will ignore these elements for now). So that means that we have a structure like:

X = .( Item1, .( Item2, []) ).

Now of course we still need to fill in Item1 and Item2. Item2 is not hard: it is the empty list [] so:

Item2 = [].

Item1 on the other hand is a list with one element, so the structure is:

Item1 = .( Item11, [] ).

With Item11 the item of that sublist. That item is fruits, so that means that:

Item11 = fruits.

If we put these all together, we obtain:

X = .( .(fruits,[]), .([],[]) ).

If we enter this in GNU-Prolog (gprolog), we get:

$ gprolog
GNU Prolog 1.4.5 (64 bits)
Compiled Feb  5 2017, 10:30:08 with gcc
By Daniel Diaz
Copyright (C) 1999-2016 Daniel Diaz
| ?- X = .( .(fruits,[]), .([],[]) ).

X = [[fruits],[]]

yes

gprolog thus can be a tool to do verification, since it will convert the dot notation into the syntactical sugar for a list.

Answer 3

In addition to what Willem wrote, you can always use write_canonical/1 to obtain the canonical representation of any term.

For example, in your case:

| ?- write_canonical([[fruits],[ ] ]).
'.'('.'(fruits,[]),'.'([],[]))

This solves the task, and shows that you have expanded the list [[]] correctly.

In particular, we have:

| ?- write_canonical([[]]).
'.'([],[])

That's right: This is a list with a single element, which is [] as indicated by the first argument of the '.'/2 term. Since it is the only element, the second argument is also [].