SICP Chapter 1 Solved with Scala


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.

About these ads

About Vikas Hazrati

Vikas is the CTO @ Knoldus which is a group of software industry veterans who have joined hands to add value to the art of software development. We do niche product and project development on Scala and Java. We consult and coach on effective software development and agile practices. With our focus on software craftsmanship you can be assured of a good quality at the right price. To know more, send a mail to info@knoldus.com or visit www.knoldus.com
This entry was posted in Scala and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s