[Haskell-cafe] Re: Type-Level Naturals Like Prolog?

[Tom Schrijvers]

On Tue, 18 Jul 2006, Jared Warren wrote:

>> >> % defining natural numbers
>> >> natural(zero).
>> >> natural(s(X)) :- natural(X).
>> >>
>> >> % translate to integers
>> >> toInt(zero, 0).
>> >> toInt(s(X), N) :- toInt(X, Y), N is Y + 1.
>> 
>> > Thank you. I can now more precisely state that what I'm trying to
>> > figure out is: what is 's', a predicate or a data structure? If it's a
>> > predicate, where are its instances? If not, what is the difference
>> > between the type language and Prolog such that the type language
>> > requires data structures?
>> 
>> it's data structure, to be exact, it's data constructor - just like,
>> for example, "Just" in Haskell. Haskell requires that all data
>> constructors should be explicitly defined before they can be used. you
>> can use "Just" to construct data values only if your program declares
>> "Just" as data constructor with "data" definition like this:
>> 
>> data Maybe a = Just a | Nothing
>> 
>> Prolog is more liberate language and there you can use any data
>> constructors without their explicit declarations, moreover, there is
>> no such declarations anyway
>> 
> [deletia]
>> 
>> i once said you about good paper on type-classes level programming. if
>> you want, i can send you my unfinished article on this topic which shows
>> correspondences between logic programming, type classes and GADTs
>
> So predicates and data constructors have similar syntax but different
> semantics in Prolog?

That is right. The syntax and naming are different from Haskell though. 
They are called respectively predicate and function symbols/functors, and 
written like f(x1,...,xn) rather than F x1 ... xn. Terms are made of 
possibly nested function symbols and variables, e.g.

 	f(f(f(a,X))) where f and a are used as function symbols

Atoms are made of a predicate symbol and terms,e.g.

 	p(f(f(f(a,X)))) where p is used as a predicate symbol
 			      f and a are used as function symbols

Note that the same name can be used with multiple argument numbers and
both as a predicate and a function symbol.

> Say, for the sake of argument, if I wanted to do
> automatic translation, how would I tell which was which in a Prolog
> program?

Based on the syntax. Basically the top-level symbols are predicate symbols
and the nested ones are function symbols, e.g. in a clause

 	p(f(X)) :-
 		q(h(i)),
 		j(k) = l(m).

p, q and '=' are predicate symbols and all the rest are function symbols.

It's probably good to read a bit about it in a proper reference. 
Wikipedia's Prolog entry lists a number of tutorials.

Cheers,

Tom
--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be