Page 1 of 1

Beginning Scheme programming

#1 Jaakuuta  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 163
  • Joined: 02-July 09

Post icon  Posted 18 July 2009 - 02:30 AM

Hello, welcome to my little Scheme tutorial.
I'm still a bit of a beginner to Scheme myself, so this will be very basic.
However, Scheme is a natural language for me and I learn it rather quickly so I'll likely be adding updates when I learn more.

Anyway, let's begin.
First off, Scheme is in a family of languages called LISP, short for list-processing. As such, the language specializes in processing lists (go figure).
Lists can be very powerful tools if used properly. You can manage entire sets of data at once using lists. There are a few peculiarities of the LISP languages that date back to its initial inception. I will make an attempt to explain these the best I can as I go along.

First things I would like to discuss about the language. The basic design of the language is oriented towards 'functional programming'. Basically, functional programming attempts to create clean, concise functions without the types of side-effects that can arise in object-oriented languages and the like.
The method for producing functions is based on Alonzo Church's Lambda Calculus. As I am not an expert at this topic, I won't go into it at depth. Suffice it to say that functions are generally formed using lambda notation derived from the lambda calculus. Also, the syntax of the language is in prefix notation like the lambda calculus (in other words instead of most languages that would say something like f(x, y) Scheme says (f x y)).

One of the cool things about Scheme is that defined data are merely symbols and can represent anything. Not only that, but certain alphanumeric characters that are normally restricted from use in naming are not restricted in Scheme. Still, it's best not to get too wild with your naming conventions. One reason I point this out is there is a specific naming convention in Scheme that all predicate symbols are followed with a ? and all symbols that cause side-effects are followed with a !

Anyway, onto some coding.
Since Scheme is a powerful calculating language, most of this tutorial will be about forming powerful calculating functions. As such I will not include the typical "Hello world" example in this tutorial. Instead I will start by giving some examples of how to form basic statements in Scheme.

First of all, there is something called 'arity' which describes how many arguments a function can have. If you attempt to use a function defined for a different number of arguments than what you have supplied, Scheme will produce an arity-error.

(+ 1 2)


This means the same as 1 + 2.

Since it's in prefix notation, even things like + and - are used at the beginning of a function. The only common exception to this is the use of complex numbers of the form #.#+#.#i .

let's try some more

 (+ (* 2 3) (/ 6 2)) 


This will yield (2 * 3) + (6 / 2) or (6 + 3) or 9

you can layer your code as deep as you want.

 (+ (* (+ (* (+ 2 3) 4) 5) (+ 2 8)) (- 7 4)) 


this would yield (((((2 + 3) * 4) + 5) * (2 + 8)) + (7 - 4))

when you get more parentheses, sometimes it's easier to add them on new lines

(+ 2
(* 3
(+ 5) ) )



or you can indent if you'd like

(+ 3
  (- 7
	(* 2 3)))



now let's introduce some basic list concepts.

There are two ways to form lists. You can either construct a list using a single data item and a list to add it onto. Or you can take two data items.
However, if you construct a list using only two data items, you'll get what is called a 'dotted pair'. This can easily be remedied by using the list keyword.

Also, Scheme reads your statements starting with the definition of the first item in the list (something like (+ 2 3) can be considered a list of 3 elements) and attempts to evaluate it. If you don't want it to be evaluated, you have to quote it. You can either do this using the keyword quote or by using '. Thus (quote a) and 'a would both yield a whereas (a) would attempt to evaluate whatever a is. If a is not defined as anything (a) would yield an error.

(cons 'a '(b c))
(cons 'a 'b)
(list 'a 'b)



The above code will yield the following:
(a b c)
(a . b)
(a b)

You can also form a list by constructing a list (via the cons keyword) using a data item and the empty list ()

(cons 'a (cons 'b (cons 'c ())))



The above code should yield (a b c) as well.

Now let's discuss breaking a list into pieces. Suppose you start out with a list such as (a b c). There are two very special keywords that can be used to access particular pieces of the list.

The first keyword is car... this is a keyword that originally meant 'contents of the address register' back when LISP was first created. Also, there is the keyword cdr... this meant 'contents of the decrement register'. The car of a list is the first data item in a list, even if that data item is a list itself. The cdr (pronounced "could-er") of a list is every element less the first one. Thus if you had a list named z that was defined as (a b c) then
(cons (car z) (cdr z))


will yield z back again.

If you want to access other elements of a list, you have to do combinations of these keywords. So, if z is still defined as (a b c) then:

(car z)
(car (cdr z))
(car (cdr (cdr z)))
(cdr z)
(cdr (cdr z))
(cdr (cdr (cdr z)))


will yield the following:
a
b
c
(b c)
( c )
()

As you may have noticed in the last example if you're only left with a list of one element, the car will be the element while the cdr will be the empty list.

Now that we've covered constructing and destructing lists, let's do something useful with this knowledge.

First, I want to tell you about the let and define keywords. The let keyword allows you to temporarily set a value to a symbol for use in a single expression. The define keyword allows you to set a value on a function until it's changed or until you end the session.

(let
( (x 2) (y 3) )
(+ x y) )



This will first set the variables x and y temporarily to 2 and 3 respectively. Then it adds them together. The value 5 should result.
Now let's try it with define.

(define x 2)
(define y 3)
(+ x y)



The first two lines will evaluate, then after the third line it will yield 5. Then if you type x or y after that they will evaluate to 2 or 3 respectively.

Let's define something a little bit more difficult. Let's make a function that will accept two values x and y and do a little arithmetic.

(define f
(lambda (x y)
(* x y) ) )



This should evaluate and say something like "function f".
Now let's make an absolute value function.

(define absol-val
(lambda (x)
(if
(< x 0)
(- 0 x)
x
)))



In this case I've introduced the if keyword.
If automatically has the so-called 'else' statement built into it.
It's a one condition keyword. It works as follows:
If - condition - consequence - alternative
However, you can form the equivalent of an if/else statement with it.

If - condition - consequence - if...

However, there is a keyword cond that takes conditional statements.

Based on the way the if keyword works, it's pretty self-evident how cond works, so I'll not cover it here.

Anyway, the above code works like so: if x is less than 0 then subtract x from 0 (hence getting the negative of the number) else return x

Now that we know how to do this, let's get into a deeper concept: recursion. Recursion allows you to define something in terms of itself. By changing the value being checked each time and setting some termination condition, one can make a clean and concise function by using recursion.
Let's use the common factorial function as an example.

(define fact
(lambda (x)
(if
(<= x 1)
1
(* x
(fact
(- x 1) ) )
)))



What this code is saying basically is that if x is less than or equal to 1 then return 1, otherwise return x * fact(x - 1)
So, if we take the number 5 for example...
(* 5 (* 4 (* 3 (* 2 1)))) -> (* 5 (* 4 (* 3 2))) -> (* 5 (* 4 6)) -> (* 5 24) -> 120

Now let's have some fun... next we're going to use the list processing that we learned earlier and our fact function we just defined and make a new function that will take a list of values such as (1 2 3 4 5) and return a new list of equal length of their factorials such as (1 2 6 24 120).

(define fact-list
(if
(eq? x ())
x
(cons
(fact
(car x) )
(fact-list
(cdr x) ) )
))



Now this function's really neat. First we check to see if x is equal to the empty list (= is only used to check numbers, thus a predicate like eq? must be used to check if it's a list) and if it is then simply return the empty list. Otherwise, construct a list of the fact of the first element and the fact-list of the rest of the list. Intuitively, this may seem difficult to grasp what's going on at first, but let me elaborate with an illustration... Suppose we started with the list (1 2 3 4 5) so the statement was

(fact-list '(1 2 3 4 5))



then it would evaluate as follows:
x is not empty -> fact of car (1 2 3 4 5) is 1, cdr x is (2 3 4 5) ->
x is not empty -> fact of car (2 3 4 5) is 2, cdr x is (3 4 5) ->
x is not empty -> fact of car (3 4 5) is 6, cdr x is (4 5) ->
x is not empty -> fact of car (4 5) is 24, cdr x is (5) ->
x is not empty -> fact of car (5) is 120, cdr x is () ->
x is empty...

This will look like
(cons (fact 1) (cons (fact 2) (cons (fact 3) (cons (fact 4) (cons (fact 5) ())))))


according to Scheme. Thus yielding (1 2 6 24 120).

Now you know some of the basics of Scheme... Have fun scheming!

This post has been edited by Jaakuuta: 19 July 2009 - 12:15 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Beginning Scheme programming

#2 naveen32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 05-September 09

Posted 05 September 2009 - 09:45 AM

View PostJaakuuta, on 18 Jul, 2009 - 01:30 AM, said:

Hello, welcome to my little Scheme tutorial.
I'm still a bit of a beginner to Scheme myself, so this will be very basic.
However, Scheme is a natural language for me and I learn it rather quickly so I'll likely be adding updates when I learn more.

Anyway, let's begin.
First off, Scheme is in a family of languages called LISP, short for list-processing. As such, the language specializes in processing lists (go figure).
Lists can be very powerful tools if used properly. You can manage entire sets of data at once using lists. There are a few peculiarities of the LISP languages that date back to its initial inception. I will make an attempt to explain these the best I can as I go along.

First things I would like to discuss about the language. The basic design of the language is oriented towards 'functional programming'. Basically, functional programming attempts to create clean, concise functions without the types of side-effects that can arise in object-oriented languages and the like.
The method for producing functions is based on Alonzo Church's Lambda Calculus. As I am not an expert at this topic, I won't go into it at depth. Suffice it to say that functions are generally formed using lambda notation derived from the lambda calculus. Also, the syntax of the language is in prefix notation like the lambda calculus (in other words instead of most languages that would say something like f(x, y) Scheme says (f x y)).

One of the cool things about Scheme is that defined data are merely symbols and can represent anything. Not only that, but certain alphanumeric characters that are normally restricted from use in naming are not restricted in Scheme. Still, it's best not to get too wild with your naming conventions. One reason I point this out is there is a specific naming convention in Scheme that all predicate symbols are followed with a ? and all symbols that cause side-effects are followed with a !

Anyway, onto some coding.
Since Scheme is a powerful calculating language, most of this tutorial will be about forming powerful calculating functions. As such I will not include the typical "Hello world" example in this tutorial. Instead I will start by giving some examples of how to form basic statements in Scheme.

First of all, there is something called 'arity' which describes how many arguments a function can have. If you attempt to use a function defined for a different number of arguments than what you have supplied, Scheme will produce an arity-error.

(+ 1 2)


This means the same as 1 + 2.

Since it's in prefix notation, even things like + and - are used at the beginning of a function. The only common exception to this is the use of complex numbers of the form #.#+#.#i .

let's try some more

 (+ (* 2 3) (/ 6 2)) 


This will yield (2 * 3) + (6 / 2) or (6 + 3) or 9

you can layer your code as deep as you want.

 (+ (* (+ (* (+ 2 3) 4) 5) (+ 2 8)) (- 7 4)) 


this would yield (((((2 + 3) * 4) + 5) * (2 + 8)) + (7 - 4))

when you get more parentheses, sometimes it's easier to add them on new lines

(+ 2
(* 3
(+ 5) ) )



or you can indent if you'd like

(+ 3
  (- 7
	(* 2 3)))



now let's introduce some basic list concepts.

There are two ways to form lists. You can either construct a list using a single data item and a list to add it onto. Or you can take two data items.
However, if you construct a list using only two data items, you'll get what is called a 'dotted pair'. This can easily be remedied by using the list keyword.

Also, Scheme reads your statements starting with the definition of the first item in the list (something like (+ 2 3) can be considered a list of 3 elements) and attempts to evaluate it. If you don't want it to be evaluated, you have to quote it. You can either do this using the keyword quote or by using '. Thus (quote a) and 'a would both yield a whereas (a) would attempt to evaluate whatever a is. If a is not defined as anything (a) would yield an error.

(cons 'a '(b c))
(cons 'a 'b)
(list 'a 'b)



The above code will yield the following:
(a b c)
(a . B)
(a B)

You can also form a list by constructing a list (via the cons keyword) using a data item and the empty list ()

(cons 'a (cons 'b (cons 'c ())))



The above code should yield (a b c) as well.

Now let's discuss breaking a list into pieces. Suppose you start out with a list such as (a b c). There are two very special keywords that can be used to access particular pieces of the list.

The first keyword is car... this is a keyword that originally meant 'contents of the address register' back when LISP was first created. Also, there is the keyword cdr... this meant 'contents of the decrement register'. The car of a list is the first data item in a list, even if that data item is a list itself. The cdr (pronounced "could-er") of a list is every element less the first one. Thus if you had a list named z that was defined as (a b c) then
(cons (car z) (cdr z))


will yield z back again.

If you want to access other elements of a list, you have to do combinations of these keywords. So, if z is still defined as (a b c) then:

(car z)
(car (cdr z))
(car (cdr (cdr z)))
(cdr z)
(cdr (cdr z))
(cdr (cdr (cdr z)))


will yield the following:
a
b
c
(b c)
( c )
()

As you may have noticed in the last example if you're only left with a list of one element, the car will be the element while the cdr will be the empty list.

Now that we've covered constructing and destructing lists, let's do something useful with this knowledge.

First, I want to tell you about the let and define keywords. The let keyword allows you to temporarily set a value to a symbol for use in a single expression. The define keyword allows you to set a value on a function until it's changed or until you end the session.

(let
( (x 2) (y 3) )
(+ x y) )



This will first set the variables x and y temporarily to 2 and 3 respectively. Then it adds them together. The value 5 should result.
Now let's try it with define.

(define x 2)
(define y 3)
(+ x y)



The first two lines will evaluate, then after the third line it will yield 5. Then if you type x or y after that they will evaluate to 2 or 3 respectively.

Let's define something a little bit more difficult. Let's make a function that will accept two values x and y and do a little arithmetic.

(define f
(lambda (x y)
(* x y) ) )



This should evaluate and say something like "function f".
Now let's make an absolute value function.

(define absol-val
(lambda (x)
(if
(< x 0)
(- 0 x)
x
)))



In this case I've introduced the if keyword.
If automatically has the so-called 'else' statement built into it.
It's a one condition keyword. It works as follows:
If - condition - consequence - alternative
However, you can form the equivalent of an if/else statement with it.

If - condition - consequence - if...

However, there is a keyword cond that takes conditional statements.

Based on the way the if keyword works, it's pretty self-evident how cond works, so I'll not cover it here.

Anyway, the above code works like so: if x is less than 0 then subtract x from 0 (hence getting the negative of the number) else return x

Now that we know how to do this, let's get into a deeper concept: recursion. Recursion allows you to define something in terms of itself. By changing the value being checked each time and setting some termination condition, one can make a clean and concise function by using recursion.
Let's use the common factorial function as an example.

(define fact
(lambda (x)
(if
(<= x 1)
1
(* x
(fact
(- x 1) ) )
)))



What this code is saying basically is that if x is less than or equal to 1 then return 1, otherwise return x * fact(x - 1)
So, if we take the number 5 for example...
(* 5 (* 4 (* 3 (* 2 1)))) -> (* 5 (* 4 (* 3 2))) -> (* 5 (* 4 6)) -> (* 5 24) -> 120

Now let's have some fun... next we're going to use the list processing that we learned earlier and our fact function we just defined and make a new function that will take a list of values such as (1 2 3 4 5) and return a new list of equal length of their factorials such as (1 2 6 24 120).

(define fact-list
(if
(eq? x ())
x
(cons
(fact
(car x) )
(fact-list
(cdr x) ) )
))



Now this function's really neat. First we check to see if x is equal to the empty list (= is only used to check numbers, thus a predicate like eq? must be used to check if it's a list) and if it is then simply return the empty list. Otherwise, construct a list of the fact of the first element and the fact-list of the rest of the list. Intuitively, this may seem difficult to grasp what's going on at first, but let me elaborate with an illustration... Suppose we started with the list (1 2 3 4 5) so the statement was

(fact-list '(1 2 3 4 5))



then it would evaluate as follows:
x is not empty -> fact of car (1 2 3 4 5) is 1, cdr x is (2 3 4 5) ->
x is not empty -> fact of car (2 3 4 5) is 2, cdr x is (3 4 5) ->
x is not empty -> fact of car (3 4 5) is 6, cdr x is (4 5) ->
x is not empty -> fact of car (4 5) is 24, cdr x is (5) ->
x is not empty -> fact of car (5) is 120, cdr x is () ->
x is empty...

This will look like
(cons (fact 1) (cons (fact 2) (cons (fact 3) (cons (fact 4) (cons (fact 5) ())))))


according to Scheme. Thus yielding (1 2 6 24 120).

Now you know some of the basics of Scheme... Have fun scheming!

Was This Post Helpful? 0
  • +
  • -

#3 naveen32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 05-September 09

Posted 05 September 2009 - 09:51 AM


(define s1 0)
(define s2 1)
(define s3 0)
(define fb 
  (lambda (s1 s2 cnt sum)   
	(cond ((= cnt 1) sum)
	(else( fb s2 (+ s1 s2) (- cnt 1)(+ s1 s2))))))




hi.... please help me in printing the value of s2 for every iteration inside the procedure fb.....

waiting for ur reply...
thanks in advance
Was This Post Helpful? 0
  • +
  • -

#4 Jaakuuta  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 163
  • Joined: 02-July 09

Posted 09 September 2009 - 03:30 AM

View Postnaveen32, on 5 Sep, 2009 - 08:51 AM, said:


(define s1 0)
(define s2 1)
(define s3 0)
(define fb 
  (lambda (s1 s2 cnt sum)   
	(cond ((= cnt 1) sum)
	(else( fb s2 (+ s1 s2) (- cnt 1)(+ s1 s2))))))




hi.... please help me in printing the value of s2 for every iteration inside the procedure fb.....

waiting for ur reply...
thanks in advance


hrm... well I didn't look over it that much, but two things I notice right off, you have the first statement after cond in parens together with the next part, also, you have an else included, usually you would use either just if/else, or cond, but not both, because cond has the conditional statements built in
Was This Post Helpful? 0
  • +
  • -

#5 khoriayton  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 15-September 09

Posted 15 September 2009 - 01:23 PM

hello everyone... Can u help me find the cube root of a number using scheme??
Was This Post Helpful? 0
  • +
  • -

#6 Jaakuuta  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 163
  • Joined: 02-July 09

Posted 17 September 2009 - 09:19 PM

One simple way that may not be the most efficient would be to create a function that would take a number and multiply it by itself twice and if it comes within a certain percentage of the desired number then it's sufficient.
something to the effect of

define cubeRoot
lambda x
let y (/ x 2) ctr 2
if (< (- (* y (* y y)) x) 0.0001)
y
if (< (* y (* y y)) x)
+ y (/ 1 ctr)
- y (/ 1 ctr)

Something to this effect, you can make it recursive and basically the idea is that you start out with some arbitrary number like one third of the original number, then if the difference of that number cubed and the actual number is not within a sufficient degree of accuracy then continue checking by adding or subtracting 1/ctr to the value
so for example, ctr starts at 2, then you start with 3 dividing it by 2 would be 3/2 which cubed would be 27/8 or 3+3/8 which is just a little over 3 so you would subtract 1/3 leading to 3/2 - 1/3 or 9/6 - 2/6 => 7/6 which cubed is 343/216, etc.

It's not the most efficient way, but its' quick and simple.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1