Re: Extended DCG?

Hi Jan,

See below…

On 13 Feb 2014, at 11:01, Jan Wielemaker <[email protected]>
 wrote:

> Hi Samer,
> 
> Ok.  I see two developments:
> 
>  - Introduction of real strings in V7 (compatible to ECLiPSe and quite
>    likely YAP at some point).
>  - Future directions to a more (soft) typed language.
> 
> There has also been fierce fights about this in the ISO group.  I don't
> know the current status.
> 
> I see several solutions:
> 
>  1. Keep phrase checking and add a new non-checking predicate.
>  2. Use Markus' state interface (exploiting push-back and a
>     one-element list).
>  3. Remove checking and add some checking library that
>     wraps phrase calls with type checking.
>  4. Only disallow string objects in phrase/3.
>  5. Auto-convert string objects in phrase/3 to code lists.
> 
> (1) is probably the best from a type-checking viewpoint. I don't know
> how to name the predicate (you seem to struggle too). I think the name
> should not refer to `gammar'. You are threading state that has nothing
> to do with the notion of grammars. Your bodies must also be limited as
> (list) literals make no sense. To me, it still seems you're misusing an
> implementation vehicle for something it was not supposed to do.  In
> my experience that is asking for a breakdown sooner or later.

This sounds ok to me. Maybe it could be called runstate/3, like in
the Haskell state monad. I don't think it's misusing anything. You make my point
for me: the list literal is the *only* operation that doesn't make sense -
all the other constructs are great and useful. To me, this suggests that
the list type checking belongs on the list literal, not on the phrase/3
predicate. Re. the point below, the one element list with push back
is just as much of a 'misuse' of the grammar system--it's just enough to
fool the putative type checker that everything is ok, but it has as much
to do with grammars as forgetting about lists and allowing any type
to be threaded. 

With full type inference, this would all work perfectly.
phrase/3 would have polymorphic type

	phrase/2 :: pred( dcg_goal(A), A, A),

where dcg_goal(A) is either a callable of type pred(A,A)
or a DCG construct involving (,), (;) (->), {} etc and subgoals
of type dcg_goal(A). The list literal would be restricted to 
list types: if X is a literal list of type list(A), then 

	X :: dcg_goal(list(A)).

As soon as a list literal appears anywhere in a DCG goal, then
the type constraint will be propagated up, so the
overall goal G will have type dcg_goal(list(A)). If you
give this as the first argument to phrase/3, then second
two arguments would have to be lists.

The only fly in the ointment is the convention of using
the empty list [] as a no-op - according to this scheme,
it's type would still be dcg_goal(list(A)) and therefore no
good for arbitrary state types. All that would be needed is
an alternative, fully polymorphic no-op, e.g. 

	noop//0 :: dcg_goal(A).
	noop(X,X).


> 
> (2) seems pretty elegant to me.  I don't really see your argument
> for `another layer of meta predicates'.  I see two rather simple
> predicates that we should be able to inline if necessary.  The
> only overhead should be a list cell.

As I said above, it seems like a needless complication and it
is just as much an abuse of the grammar mechanism as allowing
arbitrary states.

Re. the other points below, I'm a bit behind the curve with all
the developments on string representations. If a more efficient string
representation is needed, again, the only DCG operation that needs
to care is the list literal one. If the string is in a packed array
of characters, then one sensible representation of state is a 
pair (Position,String). If we let pair(X,Y) be the type of comma
separated pairs, then list literals could have several alternative types:

	<list(A)>       :: dcg_goal(list(A)).  
	<list(char)> :: dcg_goal(pair(int,string)).
	<list(code)>:: dcg_goal(pair(int,string)).

There could also be a 'string literal' which would also work
with the pair(int,string) representation. 
	<string>      :: dcg_goal(pair(int,string)).
The implementations of these in the *parsing* direction are 
obviously trivial. In the *generating* direction, the list 
representation looks like the winner.

According to this scheme, phrase/3 would *never* accept 
string in the last two argument positions. It would be reasonable,
however, to allow phrase/2 in the parsing direction to accept a 
string and convert it to either a list or a pair(int,string) according 
to the type of the DCG goal.

I realise that all of this (perhaps) requires a type system which 
SWI does not have, but my point is that adding type checking
in an ad hoc way seems like an unsatisfying half-way house -
you loose the flexibility of an untyped system but you do not
gain the power of a proper type system.

Anyway, back to the question at hand - I like option 1.  I dislike
option 2. I share your reservations about options 3,4 and 5.
I also think the pair(int,string) representation might be worth
pursuing.


cheers,
Samer


> 
> (3-5) makes we can never introduce more validation later.
> 
> (3) leaves people doing phrase("he", "hello") completely in the
> dark with a 'false'.  Unless they load some library, but that
> probably only happens after significant frustration.
> 
> (4) might be a practical solution.  Feels hacky though.  Why can I
> use an atom as a state, but not a string?
> 
> (5) Would make many things work as before, but for the wrong reason.
> If there was only phrase/2 I might have been in favor, but the result
> below is hard to explain.
> 
>  ?- phrase("he", "hello", X).
>  X = [108, 108, 111].
> 
> My preference goes to either (1) or (2), adding the predicates to
> the system and properly documenting the issue.
> 
> Support/preference/other solutions?
> Names for predicates if we go (1) or (2)?
> 
> 	Cheers --- Jan
> 
> P.s.	Ideally, I'd like something else for threading state, such as
> 	Tom's coroutining proposal, or possibly something simpler.
> 
> 
> On 02/12/2014 07:48 PM, Abdallah, Samer wrote:
>> Hi all,
>> I would just like to use this opportunity to request again that phrase/3 be
>> allowed to work with arbitrary types in the last two positions, not just
>> lists, or an alternative, say gphrase/3  (for generalised phrase), or
>> rundcg/3 which works exactly like phrase/3 but allows arbitrary types.
>> Or even better, put phrase/3 back how it was and introduce a type
>> checking list_phrase/3 or safe_phrase/3 for people who want that.
>> 
>> It used to be the case that an extended DCG for writing a transducer
>> as  Alan would like, was easy to write using ordinary DCG notation.
>> The type of the threaded argument would be a pair of lists (L,R)
>> instead of just one list. In my DCG library I have some DCG rules for
>> working with this conveniently. For example, operators (\<)//1 and (\>)//1
>> apply a DCG phrase to the left or right member of the pair:
>> 
>> :- op(800, \<, fy).
>> :- op(800, \>, fy).
>> 
>> \<(P, (L1,R), (L2,R)) :- phrase(P,L1,L2).
>> \>(P, (L,R1), (L,R2)) :- phrase(P,R1,R2)
>> 
>> Then you can do things like \< integer(X) to read an integer from
>> from the left sequence and \> [int(X)] to write a term to the right, and so on.
>> Alan's scenario is easily and efficiently dealt with.
>> 
>> Forcing us to use lists for the arguments to phrase/3 forces an ugly
>> encoding of the pair in a singleton list, e.g. as [(L,R)], and, if the list
>> is [X] and we already have a bunch of predicates that want to work
>> on X,  forces an unnecessary layer of meta-predicates to get through
>> the wrapping.
>> 
>> For the moment, I have deleted the two offending lines from boot/dcg.pl
>> in my local installations, but of course, this is not good for the portability
>> of my code!
>> 
>> cheers,
>> Samer
>> 
>> 
>> (
>> On 11 Feb 2014, at 16:51, Alan Baljeu <[email protected]>
>>  wrote:
>>> I have a scenario where I'm mapping a list to a second list, but it's not 1 to 1.  For this, it would be nice to use an extended DCG, that supports two independent lists.  Does such a thing exist?
>>> 
>>> Alan Baljeu
>>> -------------- next part --------------
>>> HTML attachment scrubbed and removed
>>> _______________________________________________
>>> SWI-Prolog mailing list
>>> [email protected]
>>> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>>> 
>> 
>> -------------- next part --------------
>> A non-text attachment was scrubbed...
>> Name: signature.asc
>> Type: application/pgp-signature
>> Size: 495 bytes
>> Desc: Message signed with OpenPGP using GPGMail
>> URL: <https://lists.iai.uni-bonn.de/pipermail/swi-prolog/attachments/20140212/e49a2d8e/attachment.bin>
>> _______________________________________________
>> SWI-Prolog mailing list
>> [email protected]
>> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>> 
> 
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.iai.uni-bonn.de/pipermail/swi-prolog/attachments/20140213/be2a6d9b/attachment.bin>