Re: DCGs as algebraic types

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.

    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.  


> 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