cs505

Maharishi University of Management

Computer Science

COMP 505: Advanced Programming Languages

Answers to selected homework excercises

Introduction to Syntax and Semantics

Watt 2.8

tExpr ::= ...
        | + sExpr
        | - sExpr
pExpr ::= ...
        | not pExpr

Formal Syntax

Watt 2.7.a

Parse of 'a or b = c':
        Expr
        +----tExpr
        |    +---tExpr
        |    |   +---Var
        |    |       +---a
        |    +---or
        |    +---sExpr
        |        +---pExpr
        |            +---Var
        |                +---b
        +---=
        +---tExpr
            +---sExpr
                +---pExpr
                    +---Var
                        +---c

Functional Programming Concepts

Michaelson 9.3.b

    fun scount (s:string) [] = 0 |
         scount (s:string) ((h::t):string list) =
            if h = s
                then 1 + (scount s t)
                else scount s t;

Michalson 9.3.c

    fun gconst (v:int) [] = [] |
         gconst (v:int) ((h::t):int list) =
            if h > v
                then h::(gconst v t)
                else gconst v t;

Type Declarations

Watt 13.5

datatype tree = null |
node of (tree * int * tree);
fun insert (newitem, null) = node (null, newitem, null) |
    insert (newitem, node (left, olditem, right)) =
if newitem <= olditem
    then node (insert (newitem, left),
        olditem,
        right)
    else node (left,
        olditem,
        insert (newitem, right));
fun treed (nil) = null |
    treed (n::ns) = insert (n, treed (ns));
fun listed (null) = nil |
    listed (node(left, n, right)) = listed (left) @ [n] @ listed (right);
listed ( treed [5, 4, 3, 2, 1] );

Higher Order Functions

Miachaelson 9.6

datatype exp = add of exp * exp |
diff of exp * exp |
mult of exp * exp |
quot of exp * exp |
numb of int;
fun eval (numb(i:int)) = i |
eval (add(e1:exp, e2:exp)) = eval(e1) + eval(e2) |
eval (diff(e1:exp, e2:exp)) = eval(e1) - eval(e2) |
eval (mult(e1:exp, e2:exp)) = eval(e1) * eval(e2) |
eval (quot(e1:exp, e2:exp)) = eval(e1) div eval(e2);
eval (add(mult(numb(1), numb(2)), diff(numb(3), numb(4))));

Watt [1] 13.7 (plus some other miscelaneous functions)

fun map f nil = [] |
map f (x::xs) = f x :: map f xs;

fun filter f nil       = [] |
    filter f (x::xs)   = if f x then x :: filter f xs
                                else      filter f xs;

fun reduce f u nil = u |
reduce f u (x::xs) = f x (reduce f u xs);

fun square x = x * x;

map square [1, 2, 3];

fun greater4 x = x > 4;

filter greater4 [2, 4, 6, 8];

fun curry f x y = f(x,y);

val $ = curry;

val sumlist = reduce ($ op+) 0;

sumlist[1,2,3];

fun upto 0 = [0] |
upto i = i::upto(i-1);

(* Actual solution to 13.7.a: *)

map (fn x => x+1) [1,2,3];

(* corresponds to {x+1 | x <- [1,2,3] } *)
(* E1 is "x+1"    *)
(* I is "x"    *)
(* E2 is "[1,2,3]"   *)

(* Actual solution to 13.7.b: *)

map (fn x => x+1) (filter (fn x => x <= 2) [1,2,3,4,5]);

Inverse Curry Function

fun inverseCurry f x y = f(y,x);

fun smallerThanFour x = inverseCurry op< 4 x;

smallerThanFour 5;

smallerThanFour 3;