SICP Chapter 1 Solved with Scala

Table of contents

Reading Time: 3 minutes

Ok, let us get the facts right. We have not provided solution to each exercise but the solutions that we have provided would be good for you to understand the concepts. It would also help you realize how efficiently we can use higher order functions in Scala.

The Structure and Interpretation of Computer Programs (http://mitpress.mit.edu/sicp/full-text/book/book.html) is a seminal book which helps you reason and understand the structure of computer programs. Though the book has been written a while back but the content is refreshingly applicable to the modern programming languages like Scala.

The github project, provides solutions to the following problems

* Exercise 1.5 and 1.6 at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html
* Exercise 1.10 at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html
* Exercises 1.34, 1.38, 1.41, 1.42 and 1.43 at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html

Here, we reproduce a couple of problems.

Exercise 1.5.  Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

(test 0 (p))

As you would notice, this problem has a direct consequence with the way the evaluation is done. There is a difference between the two approaches for applicative-order evaluation or normal-order evaluation.

object EvaluationOrder extends App {

  // Exercise 1.5 

  //Case I - Applicative order evaluation (would not terminate)
  def p : Int = p
  def test(x : Int, y : Int) = { println("Non terminating"); if (x == 0) 0 else y }

  test(0, p) // Would not terminate since p is also evaluated - 

  // Case II - Converting the second parameter to normal order evaluation
  def testTerminating(x : Int, y : => Int) = { println("Would terminate"); if (x == 0) 0 else y }

  testTerminating(0, p)

  // Case III - passing a function allows evaluation when needed hence would terminate as well
  def myFunction() : Unit = myFunction
  def testTerminatingWithFunction(x : Int, y : () => Unit) = { println("Would terminate"); if (x == 0) 0 else y }
  
  testTerminatingWithFunction(0, myFunction)

}

Let us look at another example where we are composing functions

Exercise 1.42.  Let f and g be two one-argument functions. The composition f after g is defined to be the function x  f(g(x)). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument,

((compose square inc) 6)
49

and the solution would look like

object Composition extends App {

  // Exercise 1.42

  /**
   * Compute square of a number
   */
  def square(x: Int) = x * x

  /**
   * Takes argument and adds 1 to its argument
   */
  def inc(x: Int) = x + 1

  /**
   * Take one argument functions f and g as argument
   * And implement composition x -> f(g(x))
   */
  def compose(f: Int => Int, g: Int => Int): Int => Int =   x => f(g(x))

  println(compose(square , inc)(6))  // Output is 49
}

Once you are done with the above, there is a bonus question as well

Let's model a set of integers to be a function Int -> Bool; applying that function to some integer tells us whether the integer is in the set or not.

type Set = Int -> Bool

I would like to you implement function forall, which takes some predicate p, the set to be checked and computes whether all elements in the set satisfy the predicate p. Because of the way we modelled the set, and because Int represents *a lot* of numbers, and because we want the answer 'quickly', you will need to restrict the possible range, for example from -1000 to 1000.

Thus, the final exercise to implement the function

forall :: (Int -> Bool) -> Set -> Bool

To see the solution, visit our github repository. If you feel something is missing in tacking the questions do send us your feedback either as a comment to this post or send us a mail on hello@knoldus.com We have omitted the test cases and have used objects to keep the code simple and yet display our understanding. You could write simple ScalaTest cases instead of the println that you see in the code.