INF3110 - Prolog - Oblig

prolog-types.pl

% Implementing some rules about type theory in prolog.
% This combines some of the curriculum about types and subtypes from Eyvind's lectures with 
% some SML stuff and of course Prolog.
% If you find any mistakes : send an email to morteako@student.matnat.uio.no


% 1a
% Define facts so that 
% int is a type, 
% number is a type
% a function A -> B is a type if A and B are types



% 1b
% define rules for subtyping, sub(A,B) is true if A is a subtype of B, A <: B.  
% define rules such that
% 
% int is a subtype of number
% 
% If T1 → T2 is a function type, 
%        then a subtype of it is any function S1 → S2 with the property that T1 <: S1 and S2 <: T2
% every type is a subtype of itself
% subtyping is transitive : if A is subtype of B and B is subtype of C, then A is subtype of C
% 
% It could be a good idea to split this into two predicates (this makes the rule for the transitivity easier to implement)


% 2
% define a rule to check the type of the composition of two functions.
% i.e: compose(F,G,H) should be true if (F o G) is the same type as H
% the composition of two functions can be defined as follows in SML: f o g = (fn x => f (g x)) 
% You can either derive the type yourself or see here: (b->C) -> (a->b) -> (a->c)
% You can ignore subtyping for this task




% 3a
% write rules to check if a function is in (non-trivial) curried form, meaning that it takes more than one argument
% and is in curried form 

% curried(func(int,func(int,int))). ---- true

% 3b
% find a way to count the number of arguments in a curried function. 
% for example: func(int,func(int,int)) have 2 args
% Tip : use prolog math (X is 1+Y..) and make a pred isFunc

% example
% countCurriedArgs(func(int,func(int,func(int,int))),C).  ---- C = 3




% 4a
% write rules to check if a type is a subtype of the result of applying a function to an argument
% if the function application typechecks,
% the "return" value in the 3rd argument should be the return type of the function
% funcAppl(F,A,B)  corresponds to 
% A a = ...; 
% B res = f(a);
% in java. So it should say true if this typechecks
% remember to allow for subtyping
% example
% funcAppl(func(number,number),int,number).  --- true





% 4b
% write a predicate that takes 3 lists as input: 
%	a function list, 
%	an argument type list , 
%	a resulting type list
% It should return true if the type of applying the first function to the first argument type results in the first
% result type, and so on for every element.
% It should return false if the lists have different lengths
% Hint : use funcAppl
% example : funList([func(int,int),func(number,number)],[int,int],[int,number]).   =  true