cake scip exercises

cakescip.md

Normal evaluation (lazy evaluation) model would not evaluate the operands until their values were needed. This alternative fully expand and then reduce evaluation method is known as normal-order evaluation, in contrast to the evaluate the arguments and then apply method that the interpreter actually uses, which is called applicative-order evaluation.

Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed. Delaying evaluation of procedure arguments until the last possible moment (e.g., until they are required by a primitive operation) is called lazy evaluation.

####Exercise 1.5: If the interpreter uses applicative-order evaluation, the (test 0 (p)) never terminates since the argument (p) is tried to be evaluated first. However, in normal-order evaluation, the operands are not evaluated until their values are needed. Therefore, the evaluation of (p) is deferred, and, if condition is evaluated, the predicate is true, so the result/consequent is 0.

(if <predicate> <consequent> <alternative>)

To evaluate an if expression, the interpreter starts by evaluating the <predicate> part of the expression. If the <predicate> evaluates to a true value, the interpreter then evaluates the <consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value.19

####Exercise 1.6: Since the new-if is a procedure and not a special form like if, under applicative-order evaluation, its arguments will be evaluated before its body run. Its else-clause is recursively calling the sqrt-iter, so it will never terminates.

####Exercise 1.10: positive n integer values:

(define (f n) (A 0 n)) => f(n) = 2*n
(define (g n) (A 1 n)) => g(n) = 2^n
(define (h n) (A 2 n)) => h(n) = 2^(2^(2^(…(n-1)))) which means; h(1) = 2; h(n) = 2 ^ h(n-1); 

(h 5) gives "maximum recursion depth exceeded” error because of linear recursive process.

####Exercise 1.34: It gives error of; The object 2 is not applicable. (f f) => (f 2) => (2 2) it is not a valid expression.

####Exercise 1.37:

def contFrac(n: Long => Double, d: Long => Double, k: Long): Double = {
  def loop(result: Double, i: Long): Double = {
    if (i == 0) result else loop(n(i) / (d(i) + result), i - 1)
  }
  loop(0d, k)
}

scala> contFrac(_ => 1d, _ => 1d, 100)
res0: Double = 0.6180339887498948

####Exercise 1.38:

def euler(k: Long): Double = {
  val d =  (i: Long) => if (i % 3 == 2) (i + 1) / 1.5 else 1d
  2d + contFrac(_ => 1d, d, k)
}

scala> euler(100)
res2: Double = 2.7182818284590455

####Exercise 1.41:

(define inc (lambda (x) (+ x 1)))

(define (double f) (lambda (x) (f (f x)))) 

$ (((double (double double)) inc) 5) 
result: 21

val inc = (i: Long) => i + 1
def double[A](f: A => A) = { a: A => f(f(a)) }

scala> double(double(double(double(inc))))(5)
res0: Long = 21

//((y: Long => Long) => double((x: Long => Long) => double(double(x)))(y))(inc)(5)
scala> (double((x: Long => Long) => double(double(x)))(_))(inc)(5)
res1: Long = 21
  

####Exercise 1.42:

(define (compose f g) (lambda (x) (f (g x)))) 

val inc = (i: Long) => i + 1
val square = (i : Long) => i * i
def compose[A,B,C](f: B => C, g: A => B) = (x: A) => f(g(x))

scala> compose(square, inc)(6)
res0: Long = 49

####Exercise 1.43:

(define (repeated f n) 
        (if (= n 1) 
            f 
            (compose f (repeated f (- n 1))))) 

def compose[A](f: A => A, g: A => A) = (x: A) => f(g(x))

def repeated[A](f: A => A, x: Long): A => A = {
  if (x == 1) f else compose(f, repeated(f, x - 1))
}

scala> repeated(square, 2)(5)
res0: Long = 625

###FunSets Actually, I remembered that question from Coursera course of Scala. The below is taken from my own homework.

object FunSets {

  type Set = Int => Boolean

  def contains(s: Set, elem: Int): Boolean = s(elem)

  def singletonSet(elem: Int): Set = (x: Int) => x == elem

  val bound = 1000

  def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (a < -bound) true
      else if (contains(s,a) && !p(a)) false
      else iter(a-1)
    }
    iter(bound)
  }

  def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, (x:Int) => !p(x))

  def map(s: Set, f: Int => Int): Set = (x: Int) => exists(s, (y: Int) => f(y) == x) 

}

scala> import FunSets._

scala> println(contains(map(singletonSet(1), (x:Int) => x+3), 4))
true

scala> println(contains(map(singletonSet(1), (x:Int) => x+3), 5))
false

####FunSets Poly If we parametrise the type Set with a type variable, we need to give a universal set of each type implicitly like below;

object FunSets {

  type Set[A] = A => Boolean

  def contains[A](s: Set[A], elem: A): Boolean = s(elem)

  def singletonSet[A](elem: A): Set[A] = (x: A) => x == elem

  def forall[A](s: Set[A], p: A => Boolean)(implicit bound: List[A]): Boolean = {
    !bound.exists(a => contains(s, a) && !p(a))
  }

  def exists[A](s: Set[A], p: A => Boolean)(implicit bound: List[A]): Boolean = !forall(s, (x:A) => !p(x))

  def map[A](s: Set[A], f: A => A)(implicit bound: List[A]): Set[A] = (x: A) => exists(s, (y: A) => f(y) == x)
}

scala> import FunSets._
scala> implicit val IntBound = (-1000 to 1000).toList
scala> println(contains(map(singletonSet(1), (x:Int) => x+3), 5))
false
scala> println(contains(map(singletonSet(1), (x:Int) => x+3), 4))
true

scala> implicit val longBound = (-1000L to 1000L).toList
scala> println(contains(map(singletonSet(1L), (x: Long) => x+3), 4l))
true

scala> println(contains(map(singletonSet(1.2), (x: Double) => x+3), 4.2))
<console>:18: error: could not find implicit value for parameter bound: List[Double]
       println(contains(map(singletonSet(1.2), (x: Double) => x+3), 4.2))