Project Naurk: Lecture 1

Project Naurk: Lecture 1 Ramkumar Ramachandra

October 1, 2009

Ramkumar Ramachandra

Project Naurk: Lecture 1

Expressing ideas precisely: What is a prime number?

The objective of this course is to teach students how to think precisely. We will now answer the question in plain English, and then go on to successively replace the english constructs with expressions that a machine can evaluate I

A number whose only factors are one and itself

I

A natural number that is not a multiple of any natural number except 1 and the number itself

I A

I (

natural number

natural number

that is <not a multiple of>

<not a multiple of>

any natural number except 1 and the number itself

any natural number except 1 and the number itself

Ramkumar Ramachandra

Project Naurk: Lecture 1

)

Enter: Expressions

Problem 1: Assert if 27 is a prime number. Start off by specializing the previous expression to fit this problem statement; replace the expressions highlighted in red by 27 I (

I

natural number

( 27

<not a multiple of>

<not a multiple of>

any natural number except 1 and the number itself

)

any natural number except 1 and 27 )

What’s with the parathesis? Anything that’s enclosed in paranthesis is called an expression, and it can be evaluated to produce some value. Our full expression is composed of three distinct entities. Notice how the following expression are similar. All can be evaluated to produce a value. I

( something

I

(3

I

( <square>

+

<not a multiple of>

something else )

5 ) evaluates to 8 5 ) evaluates to 25

Ramkumar Ramachandra

Project Naurk: Lecture 1

Formalizing the algorithm I

Expression (m is a choclate). This can evaluate to either True or False, depending on whether or not m is a choclate. Set our inital problem aside for a moment. Look at the following expressions: 1. (m is a choclate), where m could be any item from a mixed bag of goodies 2. (any (m is a choclate)), where m is an item from a mixed bag of goodies 3. (all (m is a choclate)), where m is an item from a mixed bag of goodies What each of these mean to a machine: 1. Pick any (random) item from the bag, and assert that it’s a choclate 2. Exhaustively pick items from the bag, and assert that any of them is a choclate 3. Exhaustively pick items from the bag, and assert that all of them are choclates Notice the design of the random experiment: we pick a random item from the bag to find out if it’s a choclate. To be able to conclusively state that all the items in the bag are choclates, we keep repeating this procedure until we’ve exhausted all the items. Hence 3 is just a restatement of 1, when we want a conclusion. 2 is entirely different.

Ramkumar Ramachandra

Project Naurk: Lecture 1

Formalizing the algorithm II

Back to our original problem. To assert if 27 is prime. Notice the remarkable similarity between these two statements. We have actually expressed our algorithm as a random experiment! 1. (m is a choclate), where m could be any item from a mixed bag of goodies 2. (27 <not a multiple of> any natural number except 1 and 27 ) To instruct the machine more concretely, let us rephrase it to get a conclusive result. After all, we do conclusively want to know whether or not 27 is prime. 1. (all (m is a choclate)), where m is an item from a mixed bag of goodies 2. ( all (27 <not a multiple of> m )), where m is a natural number not 1, not 27

Ramkumar Ramachandra

Project Naurk: Lecture 1

Enter: Literals and symbols I

(all (27 <not a multiple of> m)), where m is a natural number not 1, not 27 I

There are three pieces of data here: 1, 27 and m

I

To a machine, 1 and 27 are constants or literals that represent the integer values 1 and 27.

I

m is a symbol used to represent one value in a range of integer values. We can rewrite it as m [1, 2, 3 ..] - [1, 27] = [2, 3 .. 26, 28 ..]

I

Why did I say one value? Why not just replace the symbol m by the literal [2, 3 .. 26, 28 ..]? Because we don’t want the whole range of values, we just want one value from the range. For example, 35*[2, 3, 4 .. 34] makes less sense than 35*x where x [2, 3, 4 .. 34]1 ((all (27 <not a multiple of> m)); m [2, 3 .. 26, 28 ..] )

1

we will formalize this argument in the next slide Ramkumar Ramachandra

Project Naurk: Lecture 1

Enter: Operators

(all (27 <not a multiple of> m)); m [2, 3 .. 26, 28 ..] We will formalize the argument about picking one value from a range and binding a symbol to it. What does 35*x mean to a machine? Several definitions need to be in order: I

* is an operator defined to act on two operands

I

The symbol x could be bound to any “value”. It could be a normal integer, decimal number, complex number, or even a set of numbers. To bind, we can use another operator =, and say (x = 4) to bind x to 4.

I

More restrictions are required to be imposed on *: It is defined only when both its operands are numbers. So, an expression like (3*“ram”) is meaningless2

Notice how all is another operator- given a list of boolean values, it evaluates to a single boolean value, True or False. <not a multiple of> is a function3 (all (27 <not a multiple of> m)); m [2, 3 .. 26, 28 ..]

2 3

unless ofcourse we define such operations explicitly We have convinienty omitted the discussion of Ramkumar Ramachandra

Project Naurk: Lecture 1

Expressions II

(all (27 <not a multiple of> m)); m [2, 3 .. 26, 28 ..] Time to observe. Notice how we’ve progressively stripped out the English in favor of expressions. Now look at each one individually: 1. (27 <not a multiple of> m) 2. (all [expression in 1]) 3. [expression in 2]; m [2, 3 .. 26, 28 ..] Observe the general forms: 1. ([value] [function4 ] [value]). <not a multiple of> is clearly an function of two parameters 5 2. ([function] [expression]) => ([function] [value]) after evaluation of the expression 3. [expression] along with some additional data

4 5

the term function encapsulates operators as well operators:operands = functions:parameters Ramkumar Ramachandra

Project Naurk: Lecture 1

S-expressions

(all (27 <not a multiple of> m) ); m [2, 3 .. 26, 28 ..] From the observations on the previous slide, there are functions of two parameters like <not a multiple of>, as well as functions of one parameter like <square>. More generally there are functions of n parameters6 . Therefore, this is a more consistent way of writing expressions: ([function] [parameter 1] [parameter 2] ..) Voila! Formally, an expression written in this form is called an s-expression. Let’s rewrite our expression as an s-expression now: (all (<not a multiple of> 27 m) ); m [2, 3 .. 26, 28 ..]

6

imagine a function that adds n numbers by repeatedly using the + operator, which adds two numbers together Ramkumar Ramachandra

Project Naurk: Lecture 1

A closer look at <not a multiple of>

(all (<not a multiple of> 27 m) ); m [2, 3 .. 26, 28 ..] Now, we simply have to design the function <not a multiple

Ramkumar Ramachandra

Project Naurk: Lecture 1

Operators II

I

(all (27 <not a multiple of> m)); m [2, 3 .. 26, 28 ..]

I

Now, we have to tell the machine what M is.

I

“where M is a any natural number except 1 and 27” must now be modified to fit the definition of multiple. 27 % M = 0 is the condition for 27 being a multiple of M, provided that M ≤ 27.

I

So M is a variable number, whose value can be picked up from the set [1, 2, 3 .. 27] - [1, 27] = [2, 3 .. 26]

Ramkumar Ramachandra

Project Naurk: Lecture 1

Putting it all together

I

((27 % M) != 0); M = (any [2, 3 .. 26])

I

(all ((27 % M) != 0)); M = [2, 3 .. 26]

I

all (\ m -> 27 ‘mod‘ m /= 0) [2, 3 .. 26]

In case you haven’t noticed, the last line is a valid Haskell program!

Ramkumar Ramachandra

Project Naurk: Lecture 1

Where to go from here

I

Problem 2: Assert if 17 is a prime number. Now we have to change 27 to 17 and 26 to 16. This is a pain, especially in larger programs. So let’s just replace it by a symbol, say N. Then all (\ m -> n ‘mod‘ m /= 0) [2, 3 .. n-1] where n = 17

I

Now reuse this code to find all the prime numbers ≤ 100

Ramkumar Ramachandra

Project Naurk: Lecture 1