-- Aug 25 In-Class Exercise

'''Scheme''' GCD(14 30) 30 != 0 gcd(30 mod(14 30)) --> GCD(30 14) 14!=0 gcd(14 mod(30 14)) --> GCD(14 2) 2!= 0 gcd(2 mod(14 2)) gcd(2 0) V = 0 return U =2 '''Prolog''' GCD(U,V,U) :- V=0 <-- if V = 0 return U GCD(U,V,X) :- not (V=0), Y is U mod V, GCD(V,Y,X) <-- if V != 0 find Y (which is U Mod V) calculate GCD(V,Y,X) -?GCD(14,30) --> 30 !=0 so rule 1 doesn't work, rule 2 30 != 0 True, Calculate Y (14 mod 30) --> calculate GCD(30,14,X) -?GCD(30,14) --> 14 !=0 so rule 1 doesn't work, rule 2 14 !=0 True, Calculate Y (30 mod 14) --> calculate GCD(14,2,X) -?GCD(14,2) --> 2 !=0 so rule 1 doesn't work, rule 2 2 != 0 True, Calculate Y (14 mod 2) --> calculate GCD(2,0,X) -? GCD(2,0) 0 == 0 Rule 1 True return U =2

-- Aug 25 In-Class Exercise

 -->gcd(30,14,x)

 -->gcd(14,2,x) 

 -->gcd(2,0,x)

Prolog: gcd(14,30,14) v is not 0 so gcd(14,30,x) v is not 0 so y= 14 mod 30 aka y = 14, -->gcd(30,14,x) gcd(30,14,30) v is not 0 so gcd(30,14,x) v is not 0 so y= 30 mod 14 aka y=2, -->gcd(14,2,x) gcd(14,2,14) v is not 0 so gcd(14,2,x) v is not 0 so y= 14 mod 2 aka y=0, -->gcd(2,0,x) gcd(2,0,2) v is 0 so return 2

-- Aug 25 In-Class Exercise

((resource:IMG_20210825_184423548.jpg|Resource Description for IMG_20210825_184423548.jpg))

-- Aug 25 In-Class Exercise

Scheme: (gcd 14 30): 30 != 0, gcd 30 14 (gcd 30 14): 14 != 0, gcd 14 2 (gcd 14 2): 14 != 0, gcd 2 0 0 = 0 2 is our result for the GCD. Prologue: gcd(14, 30, X), 30 != 0, Y = 14 As a result, the program is able to move on gcd(14, 2, X), 2 != 0, Y = 0 Program is able to move on. gcd(2, 0, X) 2 = 0. U = 2 The program stops and we return 2 as our result for the gcd

-- Aug 25 In-Class Exercise

	• Program
		○ (define (gcd u v) (if (v = 0) u (gcd v modulo(u v))))
		○ u = 14
		○ v = 30

	1. V = 30 !=0 => gcd 30 (modulo 14 30) => gcd 30 14
	2. V = 14 !=0 => gcd 14 (modulo 30 14) => gcd 14 2
	3. V = 2 !=0 => gcd 2 (modulo 14 2) => gcd 2 0
	4. V = 0 => return 2

	• Program
		○ gcd(U, V, U) :- V = 0.
		○ gcd(U,V, X) :- not (V =0), Y is U mod V, gcd (V,Y,X).
		○ U = 14
		○ V = 30

	1. Query: gcd(14, 30, X)
		a. Query !=  gcd(U, V, U)
		b. Query == gcd(U,V,X)
			i. V = 30 !=0 => Y = 14 mod 30 = 14 , gcd(30, 14, X)
	2. Query: gcd(30, 14, X)
		a. Query != gcd(U, V, U)
		b. Query == gcd(U, V, X)
			i. V = 14 !=0 =>Y = 30 mod 14 = 2, gcd(14, 2, X)
	3. Query: gcd(14, 2, X)
		a. Query != gcd(U, V, U)
		b. Query == gcd(U, V, X)
			i. V = 2 !=0 => Y = 14 mod 2 = 0 , gcd(2, 0, X)
	4. Query: gcd(2, 0, X)
		a. Query == gcd(U, V, U)
			i. V == 0 => return 2

Scheme: • Program ○ (define (gcd u v) (if (v = 0) u (gcd v modulo(u v)))) ○ u = 14 ○ v = 30 1. V = 30 !=0 => gcd 30 (modulo 14 30) => gcd 30 14 2. V = 14 !=0 => gcd 14 (modulo 30 14) => gcd 14 2 3. V = 2 !=0 => gcd 2 (modulo 14 2) => gcd 2 0 4. V = 0 => return 2 Prolog • Program ○ gcd(U, V, U) :- V = 0. ○ gcd(U,V, X) :- not (V =0), Y is U mod V, gcd (V,Y,X). ○ U = 14 ○ V = 30 1. Query: gcd(14, 30, X) a. Query != gcd(U, V, U) b. Query == gcd(U,V,X) i. V = 30 !=0 => Y = 14 mod 30 = 14 , gcd(30, 14, X) 2. Query: gcd(30, 14, X) a. Query != gcd(U, V, U) b. Query == gcd(U, V, X) i. V = 14 !=0 =>Y = 30 mod 14 = 2, gcd(14, 2, X) 3. Query: gcd(14, 2, X) a. Query != gcd(U, V, U) b. Query == gcd(U, V, X) i. V = 2 !=0 => Y = 14 mod 2 = 0 , gcd(2, 0, X) 4. Query: gcd(2, 0, X) a. Query == gcd(U, V, U) i. V == 0 => return 2

-- Aug 25 In-Class Exercise

<u>Scheme</u> gcd(14, 30) gcd(30, 14) gcd(14, 2) gcd(2, 0) gcd is 2 <u>Prolog</u> gcd(14, 30, U) 30 != 0 gcd(30, 14, U) 14 != 0 gcd(14, 2, U) 2 != 0 gcd(2, 0, U) 0 == 0 gcd is 2

-- Aug 25 In-Class Exercise

'''Scheme''' ( gcd 14 30 ) -> ( 30 != 0 ) -> ( gcd 30 ( modulo 14 30 ) ) -> ( gcd 30 14 ) -> ( 14 != 30 ) -> ( gcd 14 ( modulo 30 14 ) ) -> ( gcd 14 2 ) -> ( 2 != 0 ) -> ( gcd 2 ( modulo 14 2 ) ) -> ( gcd 2 0 ) -> return 2 '''Prolog''' gcd(14, 30, 14) 30 != 0 therefore gcd(14, 30, X) -> Y is 14 mod 30, gcd(30, 14, X) -> 14 != 0, Y is 30 mod 14, gcd(14, 2, X) -> 2 != 0, Y is 14 mod 2, gcd(2, 0, X) -> 0 = 0, return 2.

-- Aug 25 In-Class Exercise

<nowiki>Scheme: (gcd 14 30) -> (v != 0) (gcd 30 14) (gcd 30 14) -> (v != 0) (gcd 14 2) (gcd 14 2) -> (v != 0) (gcd 2 0) (gcd 2 0) -> (v = 0) 2 Prolog: gcd(14,30,X) -> (30 != 0) gcd(14,30,X) -> not (v = 0), Y is 14 mod 30, gcd (30,14,X) gcd(30,14,X) -> not (v = 0), Y is 30 mod 14, gcd (14,2,X) gcd(14,2,X) -> not (v = 0), Y is 14 mod 2, gcd (2,0,X) gcd(2,0,X) -> (v = 0), X = 2</nowiki>

-- Aug 25 In-Class Exercise

Scheme GCD: (define (gcd u v) (if (= v 0) u (gcd v (modulo u v)))) Step 1:gcd(14 30) if (= v 0) is not true, so result will be gcd 30 (mod of 14 and 30) = gcd (30 14) Step 2: gcd(30 14) if (= v 0) is not true, so we continue with gcd 14 (modulo 30 14) = gcd (14 2) Step 3: gcd(14 2) if (= v 0) is not true, so we continue with gcd 2 (modulo 14 2) = gcd (2 0) Step 4: gcd (2 0) if (= v 0) is true, so return U. answer: u = 2. Prolog GCD: gcd(U, V, U) :- V = 0. gcd(U,V, X) :- not (V =0), Y is U mod V, gcd (V,Y,X). Prolog is made of rules |? - gcd(14, 30, 14) :- not (V =0), V is not 0 → Y is U mod V Y = 14 mod 30, Y = 14, gcd(30, 14, X) |? - gcd(14, 30, X) :- not (V =0), V is not 0 → Y is U mod V Y = 14 mod 30, Y = 14, gcd(30, 14, X) |? - gcd(30, 14, X) :- not (V =0), V is not 0 → Y is U mod V Y = 30 mod 14, Y = 2, gcd(14, 2, X) |? - gcd(14, 2, X) :- not (V =0), V is not 0 → Y is U mod V Y = 14 mod 2, Y = 0, gcd(2, 0, X) |? - gcd(2, 0, X) :- not (V =0), V is 0 so answer = 2

-- Aug 25 In-Class Exercise

Scheme: gcd(14,30) v ≠ 0 gcd(30,14) v ≠ 0 gcd(14,2) v ≠ 0 gcd(2,0) v = 0 Result is 2 Prolog: gcd(14,30,U) v ≠ 0 failed gcd(14,30,X) v ≠ 0 y = 14 mod 30 gcd(30,14,X) v ≠ 0 y = 30 mod 14 gcd(14,2,X) v ≠ 0 y = 14 mod 2 gcd(2,0,X) v = 0 failed gcd(2,0,U) v = 0 u = 2 Result is 2