CS 2104 Functional Programming (Continued) Lecturer : Dr. Abhik Roychoudhury School of Computing Discussion on Innermost Eval Last question of last years final Searching over infinite sorted lists Discussion in class Hamming Number List, in ascending order with no repetition, all positive integers with no prime factors other than 2, 3, or

5. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,... n as a prime factor fun scale n [] = [] | scale n (x::xs) = (n*x) :: (scale n xs) scale 2 [1,2,3,4,5] = [2,4,6,8,10] scale 3 [1,2,3,4,5] = [3,6,9,12,15] scale 3 (scale 2 [1,2,3,4,5]) = [6,12,18,24,30] Merging two Streams fun merge [] [] = [] |

merge (x::xs) (y::ys) = if x < y then x :: merge xs (y::ys) else if x > y then y :: merge (x::xs) ys else x :: merge xs ys merge [2,4,6] [3,6,9] = [2,3,4,6,9] Hamming numbers 1 scale 2 merge :: merge scale 3 scale 5 val hamming = 1 :: merge (scale 2 hamming)

(merge (scale 3 hamming) (scale 5 hamming)) Outline More about Higher-order Function Type inference and Polymorphism Evaluation Strategies Exception Handling

Exception Handling Handle special cases or failure (the exceptions) occurred during program execution. hd []; uncaught exception hd Exception can be raised and handled in the program. exception Nomatch; exception Nomatch : exn fun member(a,x) = if null(x) then raise Nomatch else if a = hd(x) then x else member(a,tl(x)) fun member(a,x) = if null(x) then raise Nomatch else if a = hd(x) then x else member(a,tl(x)) member(3,[1,2,3,1,2,3]) ; val it = [3,1,2,3] : int list

member(4,[]) ; uncaught exception Nomatch member(5,[1,2,3]) handle Nomatch=>[]; val it = [] : int list CS 2104 Prog. Lang. Concepts Logic Programming I Dr. Abhik Roychoudhury School of Computing Prolog The only popular logic programming language. Short for Programming in Logic. Programs are first order logic formulae.

Clean formal semantics. Procedural language. Procedures are called predicates. Prolog Rather unusual compared to imperative languages. How to start studying it ? Logic - Usual approach. Programming - Our approach

[Draft Book: Programming in Tabled Prolog] Refer : Chapter 2 of this online book [by Prof. David S. Warren, SUNY Stony Brook] http://www.cs.sunysb.edu/~warren Procedural nature Prolog is a procedural language like PASCAL. Write procedure/subprograms to carry out specific tasks. Features of Prolog procedures (predicates) Assign once variables

Only one value ever gets assigned to a variable. Nondeterminism Multiple definitions of the same procedure. Assign Once variables At any point of program exec, any Prolog variable V

Cannot have For (I = 1 ; I < = 10; I++) Sum := Sum + I Instead, how about Has a value, which will never be changed Or, does not have a value yet. Sum(0) = 0 Sum(I) = Sum(I 1) + I Sum(0), Sum(1), Sum(2),

if I > 0 . are all distinct vars. Summing of 1..N add(N, Sum) : If N = 0 then Sum := 0 else add(N 1, Sum1) Sum := Sum1 + N The above is not Prolog syntax, but shows its procedural nature with assign once variables.

Recursion and iteration add is a recursive procedure. Instead of iterating over I, add issues recursive invocation. Each recursive invocation of add results in a new Sum var. Recursion and iteration Instead of one Sum var. getting many values

Multiple sum variables. Each gets one value. This is only the programming style, do not worry about efficiency of implementation. General technique of modeling iteration via recursion new variable for each recursive invocation

Symmetric Assignment Variables are assign once. LHS and RHS of assignment no difference X := 0 X := Y 0 := X Y := X If X,Y are assign-once there can be only one reasonable semantics for both sequences.

Symmetric Assignment X := 0 X := Y X 0 0 Y

0 0 := X Y := X X 0 0 Y 0 A var. is , if no value has been assigned yet. Even re-orderings of such symmetric assignments will give the same result Why ? Test and Assignment

X := Y Before this assignment executes: Case 1: X = , Y = Future assignments of X and Y must match Case 2: X = , Y = v (some value) X is assigned the value v Test and Assignment Case 3: Y = , X = v (some value)

Y is assigned the value v Case 4: X = v1, Y = v2 Test whether the values v1 and v2 are same With assign once variables, just one operator for both test and assignment. Call it = Sum of 1..N - Revisited add(N, Sum) : ( N = 0 -> Sum = 0

; N1 is N 1, add(N1, Sum1), Sum is Sum1 + N ). ->, ; is : denotes if-then-else special case of = for arith. expr. So far

Prolog is procedural. Variables are assign once. Assignment is symmetric. Same operator for test and assignment Call this unification more later Now Data Structures in Prolog

Unification Lists, Trees, Terms Pattern Matching Test and Assignment Non-determinism in Prolog Data Structures in Prolog No data types. Every data is a term. Terms are trees constituted from

Integers 1, -1, 2, Float - 3.14159, 2.0, Other constants- a,b,c (small letters) Other terms A term represents itself. Examples of terms

1 3.14159 f(a) where no meaning has been assigned to f f(g(a, b), c) F(g(a,b), 1, h(d)) Prolog variables written in capital letters: X, Y, Z, Variables get assigned to terms via program Exec. Prolog Lists [] [1,2,3]

[or, not, [b, 1], 3.1415] [H|T] list with head H, tail T [a,H2|T] list with a, H2, followed by T Sum of an array of integers add(List, Sum) : ( List = [] -> Sum = 0

; List = [Head|Tail], add(Tail, TailSum), Sum is TailSum + Head ). Unification List = [ Head | Tail] If Head, Tail assigned already, constructs List (assignment of List). If List assigned already, assigns head of List to Head, tail of List to Tail List could even be partially instantiated

[a, b, c | X] More powerful than X = Y Unification Combines the power of Pattern matching (discussed for FP) Symmetric assignment Test Sum is TailSum + Head Evaluate the expression TailSum + Head Assign this value to Sum This is not unification.

Appending two lists append(L1, L2, L3) : ( L1 = [] -> L3 = L2 ; L1 = [X|L1Tail], % Consume L1 append(L1Tail, L2, L3Tail), L3 = [X|L3Tail] % Produce L3 ). Other correct variations follow Look closely !! Append Version 2

append(L1, L2, L3) : ( L1 = [] -> L3 = L2 ; L3 = [X|L3Tail], % Produce L3 L1 = [X|L1Tail], % Consume L1 append(L1Tail, L2, L3Tail) ). Constructing L3, even when L3Tail = Non-determinism A prog. lang is deterministic if

For any point in program execution always exactly one next step (command) A Prolog procedure (predicate) may have multiple definitions (clauses). The applicability of these definitions is not mutually exclusive. Example

friend(X, Y) :- X = mary, Y = cindy. friend(X, Y) :- X = mary, Y = emily. To find the friends of mary User asks the question friend(mary, Z) Underlying execution has two choices Choose first rule, return Z = cindy Choose second rule, return Z = emily. How would this be programmed in FP ? Append program Revisited

append(L1, L2, L3) :L1 = [], L3 = L2. append(L1, L2, L3) :L1 = [X|L1t], append(L1t,L2,L3t), L3=[X|L3t]. The two clauses are mutually exclusive, or are they ?? If not, then non-determinism in execution !! One program many tasks Depends on how we use this program. Prolog program execution triggered by asking a question (query).

Query 1: ?- append([a,b],[c,d,e,f],X) Append two given lists, and return this list in X. Execution is deterministic. Similar to the way append function works in FP. One program many tasks Query 2: ?- append([a,b],[c],[a,b,c])

Verifies that the result of appending the first two arguments is indeed the third argument. Execution is deterministic. Query 3: ?- append([a,b],X,[a,b,c]) Which list when appended with [a,b] gives [a,b,c] Execution is deterministic. One program many tasks Query 4: ?- append(X,Y,[a,b,c])

Execution is non-deterministic. Returns all possible X, Y such that by appending them the list [a,b,c] is obtained X X X X = = = =

[], Y = [a], Y = [a,b], Y [a,b,c], [a,b,c] [b,c] = [c] Y = [] Membership in a list

member(X, [X|L]). member(X, [Y|L]) :- member(X, L). Clauses of the form (Head :- Body). Unifications can be moved to Head. Can ask the queries member(1, [1,2,3]). member(X, [1,2,3]). Non-deterministic computation

member(X, [1,2]) X=1 member(X, [2]) X=2 member(X, []) fail Query Evaluation Prolog computation proceeds by query evaluation. Query evaluation is non-deterministic

Each clause of the form (Head :- Body.) There can be > 1 clause whose head unifies with the query Example : The query member(X, [1,2,3]) Evaluation of a query Q in a Prolog program P Checks which clause heads of P unify with Q Let these clauses be {c1,c2,,cn} Evaluate the bodies of {c1,c2,,cn} in program P. Query Evaluation of member

Query : member(X, [1,2]) Program: member(X, [X|L]). member(X, [Y|L]) :- member(X, L). Step 1: Unifies with both clauses. First clause: Unify X = 1, L = [2]. Body = null Second clause: Unify Y = 1, L = [2]. Body = member(X, [2]) Query Evaluation of member

Step 2: Need to evaluate member(X, [2]) Unifies with both clauses of program. First clause: Unify X = 2, L = [] Body = null Second clause: Unify Y = 2, L = [] Body = member(X, []) Step 3: Need to evaluate member(X, []) Unifies with no program clause.

Computation fails. Failure and Nondeterminism Evaluating query Q in program P Q unifies with no clause head of P - failure Q unifies with exactly one clause head deterministic step. Q unifies with > 1 clause head

Non-determinism. Multiple answers for query Q in program P. Example: member(X, []) fails member(X, [1,2]) produces > 1 assignments for X (answers) Summary: Prolog execution Evaluating member(X, [1,2]) Invoking the member subprogram with parameters

Since 2 unifying clauses 2 execution paths X, [1,2] Think of these 2 definitions (clauses) running on 2 different Machines : M1 , M2 M1 terminates and produces the assignment X = 1. M2 goes on to evaluate member(X, [2]). Summary: Prolog execution

Evaluating member(X, [2]) Invoking the member subprogram with parameters Since 2 unifying clauses 2 execution paths X, [2] Think of these 2 definitions (clauses) running on 2 different Machines: M3, M4

M3 terminates and produces the assignment X = 2. M4 goes on to evaluate member(X, []). Evaluating member(X, []) No unifying clauses, M4 aborts after reporting failure Exercises Write Prolog predicates for

Reversing a list Insertion sorting a list Merging two sorted lists In what unusual ways can you use them (which is not possible in C) ? Implement BST operations in Prolog.