Declarative programming (course in English)
Spring 2007

Homework

Those who don't yet have the signaure have to hand in minimum 7 homeworks. The solutions are checked face-to-face, and have to be checked before the exam. You have to send your homeworks to both the addresses bekesa at sch dot bme dot hu and patai at iit dot bme dot hu. The deadline is 24 hours before the start of the exam you want to take. On the exam we start with examining your homeworks. If you can't prove that you have written the programs on your own (by proving that you fully understand your code), you may not start the exam. It's a good idea to hand in and have your homeworks checked in an earlier exam than you want to take.

1st exercise - SML (2nd April)

Implement an SML function that takes an integer and converts it to another integer, which contains only the digits 0 and 1, and it represents the original number when interpreted as a base-2 value. 
(* 
int2bin: int -> int
int2bin x = y, where all digits of y are either 0 or 1,
and they represent x when interpreted as a base-2 number.
*)
Do not use lists or other composite data structures, since the task can be solved using only data of type int.

2nd exercise - Prolog

Implement a Prolog predicate that takes an integer and converts it to another integer, which contains only the digits 0 and 1, and it represents the original number when interpreted as a base-2 value. 
% int2bin(+X,?Y), where both X and Y are integers, all digits of Y are
% either 0 or 1, and they represent X when interpreted as a base-2 number.
Do not use lists or other composite data structures, since the task can be solved using only integers.

3rd exercise - SML

Implement an SML function that takes an integer and converts it to a string, which contains only the characters 0-9 and A-F, and it represents the original number when interpreted as a base-16 value. 
(* 
int2hex: int -> string
int2hex x = y, where all characters of y are either 0-9 or A-F,
and they represent x when interpreted as a base-16 number.
*)

4th exercise - Prolog

Implement a Prolog predicate that takes an integer and converts it to a string, which contains only the characters 0-9 and A-F, and it represents the original number when interpreted as a base-16 value. 
% int2bin(+X,?Y), where X is an integer and Y is a string that contains
% only the characters 0-9 and A-F, and it represents X when interpreted
% as a base-16 number.

5th exercise - Prolog

Let rat(Num,Den) (Num and Den are integers) denote the rational number with numerator Num and denominator Den. Implement a Prolog predicate that evaluates an arithmetic expression built from integers, rational numbers of the form rat(Num,Den) and the operators +,-,*,/, and produces the result as a rational number. The final result must be simplified, but the predicate can use any form of data internally. Make sure that the predicate succeeds exactly once. 
% rat_eval(+X,?Y), where
% - X is an arithmetic expression built from integers, rational numbers
%   of the form rat(Num,Den) and the operators +,-,*,/
% - Y = rat(Num,Den), and X evaluates to the rational number Num/Den
%
% Example:
% rat_eval(1/(1+2)+rat(3,9),Y) => Y = rat(2,3) % not rat(6,9)!

6th exercise - Prolog - an enhancement of the previous exercise

Implement a Prolog predicate that evaluates an arithmetic expression built from integers, floating point numbers, rational numbers of the form rat(Num,Den), constants and the operators +,-,*,/, and produces the result as a rational number.

Constants are atoms, whose values are defined by a list that contains Name-Value pairs. E.g. the list [x-1.5,y-rat(1,3)] specifies that x equals 1.5 and y is 1/3.

Floating point numbers must be converted to rationals with the given precision: a real number X is considered equal to any rational rat(Num,Den), if X-Precision < Num/Den < X+Precision. The simplest way to produce such rational numbers is using the formula rat(integer(X*Y),Y), where Y can be obtained by starting from 1 and increasing it (e.g. repeatedly multiplying by 10) until the inequality given above holds. 
% rat_eval(+X,+Constants,+Precision,?Y), where
% - X is an arithmetic expression built from integers, reals, rational
%   numbers of the form rat(Num,Den), constants and the operators +,-,*,/
% - Y = rat(Num,Den), and X evaluates to the rational number Num/Den
%
% Example:
% rat_eval(x*2/3.0+y*rat(1,6),[x-0.50812,y-2,z-12345],0.1,Y) => Y = rat(2,3)

7th exercise - SML

Implement the String.tokens function of the SML Basis Library. Description of the function here.

8th exercise - Prolog

Similar to the 7th (SML) exercise: implement a tokenising predicate. 
% tokens(+Sentence,+Delimiters,?Words), where
% - Sentence and Delimiters are strings. Words is a list of strings.
% - Words contains the words of Sentence (in the original order).
% Delimiters is the list of characters that act as separators between
% the tokens.
%
% Example:
%
% tokens("Hello World!"," ",X) -> X = ["Hello","World!"]
% tokens("a1b2cde3","12345",X) -> X = ["a","b","cde"]
% tokens("a b c",[],X)         -> X = ["a b c"]

9th exercise - SML

Calculating the union of sets represented by ordered lists. 
(*
union: ('a * 'a -> order) -> 'a list list -> 'a list
union compare sets = The union of sets given in the second argument
as a list of sets, where the elements of each set are ordered using
the ordering relation called "compare"

Examples:

union Int.compare    []                              = []
union String.compare [ ["a","b"] ]                   = ["a","b"]
union Int.compare    [ [1], [], [0,1,2,3] ]          = [0,1,2,3]
union Char.compare   [ [#"a"], [#"b"] ]              = [#"a",#"b"]
union Int.compare    [ [1,2,3], [2,3,4], [0,1,2,3] ] = [0,1,2,3,4]
*)

10th exercise - Prolog

Calculating the union of sets represented by ordered lists. 
% union(+Sets,?Union), where ahol Sets is a list of lists ordered with
% respect to the standard total ordering of terms defined in Prolog (@<),
% and Union is the union of these sets.
%
% Examples:
%
% union([], X)                                -> X = []
% union([ [1,a] ], X)                         -> X = [1,a]
% union([ [1,a], [] ],X)                      -> X = [1,a]
% union([ [1,2,3], [2,3] ], X)                -> X = [1,2,3]
% union([ [1,b,c], [2,3,a,b] ], X)            -> X = [1,2,3,a,b,c]
% union([ [A,C], [B,C] ] ,X)                  -> X = [A,B,C]
% union([ [A,1,a,b(X),b(1)], [B,3,b(A),b(1)] ], X) -> X = [A,B,1,3,a,b(A),b(X),b(1)]

11th exercise - Prolog

Evaluating logic expressions. A logic expression is one of the following: 
true,
false,
not(Logic_expr),
and(Logikai_kif,Logikai_kif),
or(Logikai_kif,Logikai_kif)
or, with Prolog-style type definition: 
%type logi ---> {true};{false};{and(logi,logi)};{or(logi,logi)};{not(logi)}
Write a Prolog procedure that evaluates logic expressions. 
% eval(+Expr,?Result), where Expr is a logic expression (of type logi)
% and Result is the value of Expr (ie. either true or false)
%
% Examples:
%
% eval(true, X)                           -> X = true
% eval(false, X)                          -> X = false
% eval(and(true,false),X)                 -> X = false
% eval(or(and(false,not(true)),true), X)  -> X = true

Enhancement:

and and or can contain an arbitary number of logic expressions (but at least one). Examples: 
eval(and(true),X)                           -> X=true
eval(and(true,true,true,false,true),X)      -> X=false
eval(or(true,true,true,false,true),X)       -> X=true
eval(or(and(true,true,false),or(true,true,false),true),X)       -> X=true
Remark: You'll need the univ ('=..') built-in procedure and mutual recursion.

12th exercise - SML

Evaluating logic expressions. For storing logic expressions we use the following type: 
datatype logi = Const of bool | And of logi * logi | Or of logi * logi | Not of logi;
Write an SML function that evaluates logic expressions. 
(*
eval: logi -> bool
eval(Expr) = the result of evaluating Expr

Examples:

eval(Const true)			    = true
eval(Const false)                           = false
eval(And(Const true,Const false))           = false
eval(Or(And(Const false,Not(Const true))))  = true
*)

Enhancement:

And and Or structures contain list of logi's. 
datatype logi = Const of bool | And of logi list| Or of logi list | Not of logi;
If an And or Or contains an empty list, throw an exception! Examples: 
eval(And[Const true])                                       = true
eval(And[])                              => exception: Illegal_logi
eval(And[Const true,Not(Const false),Const false])          = false
eval(And[Const true,Or[Const true,Const false],Const true]) = true
Remark: can be solved without mutual recursion.