HOME

9. IO

Yet Another Scheme Tutorial

11. Characters and Strings

Post Messages

10. Assignment

1. Introduction

Even assignment is convenient and easy to understand, it has substantial drawback. See SICP: 3.1 Assignment and Local State and Why Functional Programming Matters.

Forms for assignment defined in R⁵RS are set!, set-car!, set-cdr!, string-set!, vector-set! and etc. In addition there are several implementation depending assignment forms. As assignment changes values of parameters, it is called destructive. In Scheme, names of destructive operators end with ! to warn programmers.

2. set!

(define var 1)
(set! var (* var 10))
var ⇒ 10

(let ((i 1))
    (set! i (+ i 3))
    i)
⇒ 4

3. Assignment and Internal status

3.1. Static Scope (Lexical Closure)

The let, lambda, and letrec form make closures. The arguments of lambda expression are valid in the function definition. As let is a syntax sugar for lambda, the same thing happens.

3.2. Implementation of Internal States using the Lexical Closure and Assignment

(define bank-account
  (let ((balance 10))
    (lambda (n)
      (set! balance (+ balance n))
      balance)))

(bank-account 20)     ; donating 20 dollars 
;Value: 30

(bank-account -25)     ; withdrawing 25 dollars
;Value: 5

As you can write procedures that returns a procedure using Scheme, you can write a function that create 'bank account'.
This example implies that it is easy to make an object oriented (OO) language using functional programming language. In fact, only few more is required from here to make an OO language.

(define (make-bank-account balance)
  (lambda (n)
    (set! balance (+ balance n))
    balance))

(define gates-bank-account (make-bank-account 10))   ; Gates makes a bank account by donating  10 dollars
;Value: gates-bank-account

(gates-bank-account 50)                              ; donating 50 dollars
;Value: 60

(gates-bank-account -55)                             ; withdrawing 55 dollars
;Value: 5


(define torvalds-bank-account (make-bank-account 100))  ; Torvalds makes a bank account by donating 100 dollars
;Value: torvalds-bank-account

(torvalds-bank-account -70)                             ; withdrawing 70 dollars
;Value: 30

(torvalds-bank-account 300)                             ; donating 300 dollars
;Value: 330

3.3. Side effect

Exercise 1

4. Destructive Operations on Lists (set-car!, set-cdr!)

(define tree '((1 2) (3 4 5) (6 7 8 9)))

(set-car! (car tree) 100)  ; changing 1 to 100 

tree
 ((100 2) (3 4 5) (6 7 8 9))

(set-cdr! (third tree) '(a b c)) ; changing  '(7 8 9) to '(a b c) 

tree
⇒ ((100 2) (3 4 5) (6 a b c))

4.1. Queue

Queue can be implemented by using set-car! and set-cdr!. Queue is a first in first out (FIFO) date structure while ordinary list is first in last out (FILO). Figure 1 shows the data structure of queue. The pointer of the car part of cons-cell-top points to the list and that of the cdr part to the last cons cell of the list.

Figure 1: The data structure of queue.

Enqueue is performed with following procedure (Fig. 2):

1. Redirecting the cdr part of the last cons cell which is accessible directly by (cdr cons-cell-top) to a new item.
2. Redirecting the cdr part of cons-cell-top to the new item.

Figure 2: The procedure of adding 'item 4' to the queue.

Dequeue is performed with following procedure (Fig. 3)

1. Storing the top item of the list to a local variable.
2. Redirecting the car part of the cons-cell-top to the second item of the list.

Figure 3: The procedure of popping 'item 1' from the queue.

[code 1] shows a implementation of queue. The function enqueue! returns a queue in that the obj is added at the last of the queue. The function dequeue! removes the first item from the queue and return the first item.

[code 1]

(define (make-queue)
  (cons '() '()))

(define (enqueue! queue obj)
  (let ((lobj (cons obj '())))
    (if (null? (car queue))
	(begin
	  (set-car! queue lobj)
	  (set-cdr! queue lobj))
	(begin
	  (set-cdr! (cdr queue) lobj)
	  (set-cdr! queue lobj)))
    (car queue)))

(define (dequeue! queue)
  (let ((obj (car (car queue))))
    (set-car! queue (cdr (car queue)))
    obj))

(define q (make-queue))
;Value: q

(enqueue! q 'a)
;Value 12: (a)

(enqueue! q 'b)
;Value 12: (a b)

(enqueue! q 'c)
;Value 12: (a b c)

(dequeue! q)
;Value: a

q
;Value 13: ((b c) c)

(define (make-bank-account amount)
  (lambda (n)
    (let ((m (+ amount n)))
      (if (negative? m)
	  'error
	  (begin
	    (set! amount m)
	    amount)))))