Re: DCGs as algebraic types

On 13/11/2013, at 04:26, Stassa Patsantzis <[email protected]> wrote:

> Hi Richard,
> 
>> The one time I tried to discourage someone with an original idea,
>> it became a major subarea of CS with multiple journals and conferences
>> twelve years later.  I'm not going to do that again!
> 
> No, I think you're right, a lot of what I wrote last time sounds a bit sloppy or
> just based on an incomplete understanding of DCGs. It's not going to hurt my 
> feelings if you say so but what I'm really worried about is wasting your time. 
> 
> You don't have to worry about discouraging me, I'm not trying to write a paper 
> or do research. I'm not in academia, I have some long term plans to write an 
> application in Prolog and try to see if I can get some people interested in 
> forming a small community around it. To do that I'd like to find a way to write 
> Prolog in a bit more structured manner. It looks like some sort of Haskell-like 
> type system is the way to go, or one way to go, so I'm exploring in that general 
> direction. I had a look at Logtalk and Mercury, constraint logic programming and
> attributed variables already, so this DCGs as adts idea is just one thing I'm 
> looking into that seemed interesting. In any case ideas are a dime a dozen, the 
> important thing is to write code that does the job. 
>  
> You suggested a few sources that seem useful, in particular "Patterns for Prolog 
> Programming" and "Stepwise Enhancement and Higher Order Programming in Prolog". 
> When I ask questions in this list, it's usually to find out if there is a 
> pattern to solve my problems, something that's unfortunately more difficult to 
> find in Prolog than in more popular languages. The titles above sound promising, 
> I'll see if I can find a copy. 
> 
> 
>>>      list --> [].
>>>      list --> [H], { type([H], []) }, list.
>>> 
>>>      type --> [t] | [y] | [p] | [e].
> 
>> That's a long-winded way to write
> 
>>     list --> [].
>>     list --> [H], {member(H, [t,y,p,e])}, list.
> 
> Of course. I'm not saying that because I bound a list to a grammar rule it's 
> suddendly mystically transformed into a unique and magical thing that's not a 
> list anymore. What I want to do is declare more type//0 predicates in separate 
> modules, then create lists of module-specific type//0's. I'd better give an 
> example of what I mean: 
> 
>     :-module(a_type, [type//0]).
> 
>     type --> [a_type].
> 
> 
>     :-module(member1, []).
>     :-use_module(a_type).
>     :-add_import_module(member1, a_type, start).
> 
>     type --> [member1].
>     
> 
>     :-module(dcg_list, [list//0]).
>     :-use_module(a_type).
>     :-use_module(member1).
> 
>     list --> [].
>     list --> [H], { type([H], []) }, list.

Why not simply:

    list --> type, list.

Or am I missing something?

>     type --> a_type:type.
>     type --> member1:type.
> 
> Then (disregarding warnings about weak overrides): 
> 
> ?- phrase(list, [a_type,member1]).
> true .
> ?- phrase(list, [a_type,member1,stassa]).
> false.
> 
> Ideally type//0 would be module-qualified in the body of list//0, so I think I 
> need to have list//0 as a meta predicate. I haven't got around to doing that yet
> though. I can't see how to do that with member/2 inside the body of list//0, not 
> without much clutter, but I'm possibly missing something. I've picked up modules
> relatively recently.

No need for meta-predicates or calls to member/2. The equivalent solution in Logtalk (since you mention it above) is:

:- protocol(types).

	:- public(type//0).

:- end_protocol.


:- object(a_type,
	implements(types)).

	type --> [a_type].

:- end_object.


:- object(member1,
	implements(types)).

	type --> [member1].
    
:- end_object.


:- object(dcg_list).

	:- public(list//0).
	list --> [].
	list --> type, list.

	type --> a_type::type.
	type --> member1::type.

:- end_object.

It works as you expect:

?- dcg_list << phrase(list, [a_type,member1]).
true ;
false.

?- dcg_list << phrase(list, [a_type,member1]).
true ;
false.

?- dcg_list << phrase(list, [a_type,member1,stassa]).
false.

Cheers,

Paulo

>> I don't know.  I don't even know how you propose to represent a
>> grammar as lists.  Try it and find out.
> 
> I think what I was trying to say there was back-to-front. I was thinking of the 
> list of tokens passed to a DCG, rather than the DCG itself. Apologies- I don't 
> always have the language to say what I'm thinking (which means I'm not thinking 
> very clearly). 
> 
> Oh, I did read the wikipedia article on JSP. I kind of jumped ahead of myself 
> with the input/output thing, sorry. I think I see what you mean about missing 
> the point if I think of DCGs as imperative or functional. 
>     
> 
>>> I think the above is pretty similar to my example, especially the revised one. 
>>> "call(A,H)" is very much like "type([H], [])" I think, where A is type//0. 
>     
>> It's not that similar.  call(A, H) says "given that A is a term naming a
>> type, which is represented by a system of clauses, check that data term
>> H belongs to that type."  type([H], []) is a long-winded way of saying
>> that H must be one of a *specific* set of values.  The lists here serve
>> no purpose, and the "type parameter" A is missing.
> 
>> The argument order here is "type terms, data term" so that we can
>> do things like call('T3'(list(list('Int'))), X).
> 
> Is there such a huge difference between "a system of clauses" and "a list of 
> terms that can be predicate heads"? "A set of values", well, isn't that a type, 
> really? I don't have the theoretical background to go in depth on this, but from 
> where I'm looking at it and for my purposes ('more' structured programming) what
> I want from a type is some security that when I bind a variable to a value, I 
> know what kind of value that is. 
> 
> The fact that the type parameter is missing worries me more. I couldn't see a 
> way to get that in my grammar without adding an argument to list//0, which must
> mean I'm doing it wrong, because then I can't see the resulting list//1 as an 
> obvious translation of the plain predicate 'List'/2 anymore. I think the problem 
> is that "type([H], [])" can't take any more input, but it's getting a bit late
> now, so I'll excuse myself here. 
> 
> Thank you very much for the input and your patience, like I say I hope I didn't
> waste your time. 
> 
> Btw, I'm dying to ask about that major subarea of computer science, if it's not
> too traumatic :) 
> 
> Cheers!
> Stassa
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:[email protected]>
Web:   <http://logtalk.org/>
-----------------------------------------------------------------