Re: DCGs as algebraic types

> Hi list,
>
> When I look at a grammar rule like the following:
>
> list --> [].
> list --> [H|T], { list(T,[]) }.

That second rule is exceptionally strange.  I am away from home
and do not have ready access to the draft DCG specification for
the standard, but it's not even clear to me that it is legal.
A list of terminals must be a *proper* list.

>
> - I can't help but think that it looks a lot like an algebraic data type.
> Say
> for instance, the following example from wikipedia:
>
> data List a = Nil | Cons a (List a)

That corresponds to a plain predicate:

    'List'(A, 'Nil').
    'List'(A, 'Cons'(H, T)) :-
        call(A, H),
        'List'(A, T).

The general construction should be fairly obvious.
There is a predicate for each type constructor, having
one data argument (the last), and an argument for each
type parameter.  There is a clause for each data constructor.
This approach is not limited to ADTs but can handle GADts as
well.

The analogy between data types and grammars has been known
longer than Prolog has existed; it's one of the key ideas
behind Jackson Structured Programming.

> So does that all sound too naive? Or did I just reinvent someone's wheel?
> Is
> there any good reason why not to use DCG's to do type checking like above?

You _have_ reinvented a wheel, but it's a good firm properly circular
wheel with a lot of mileage left.  There is bound to be some more
insight to be won from it.  As there are interesting classes of
grammars, are there interesting classes of types?  What if you think
about Tree and/or Graph grammars instead of sequence grammars?  What
does Jackson's idea of a "structure clash" have to teach us about
writing Prolog code?

But yes, there is a reason not to use DCGs for type checking: most
data types are not lists.