Sketchy LISP

An Introduction to Functional Programming in Scheme

2.5 Type Conversion

Sometimes it would make sense to apply a procedure that is specific to one type to a different type. For example, it would be nice if the reverse procedure could be used to reverse strings. However, reverse expects an argument of the type list. This is where type conversion comes into play. The string->list and list->string procedures convert strings to lists and vice versa. With their help, reverse can be used to reverse a string:

(list->string
  (reverse
    (string->list "Hello, World!")))
=> "!dlroW ,olleH"

The conversion of one type to another is not the same as type casts in weakly typed languages. A type cast tells a compiler that it should treat an object of a given type as an object of another type, even if this is not the case. A type conversion, though, creates a new object of the desired type that resembles the object to be converted. For example, string->list creates a list containing the same sequence of characters as a given string

(string->list "Hello World!")
=> (#\H #\e #\l #\l #\o #\space #\W #\o #\r #\l #\d #\!)

and list->string converts a list of characters into a corresponding string.

There are more type conversion procedures in Scheme, like these:

char->integer  string->symbol  list->string  list->vector
integer->char  symbol->string  string->list  vector->list

There is not a conversion procedure for every possible conversion. For instance, there is no symbol->list procedure, because it would rarely be used, and even if you would need it, it could easily be written by composing string->list and symbol->string:

(define (symbol->list x)
  (string->list (symbol->string x)))

In early versions of LISP there was no char type, so single characters were represented by single-character symbols, and there was a procedure that decomposed multi-character symbols into lists of single-character symbols. This procedure was called explode. Using above definition of symbol->list, it can easily be re-written in Scheme:

(define (explode x)
  (map (lambda (x)
         (string->symbol (string x)))
       (symbol->list x)))

This procedure first converts the symbol passed to it into a list of chars. Then it maps a procedure over that list which converts each member back into a symbol. String is a variadic procedure that creates a new string from its arguments:

(string #\f #\o #\o) => "foo"

The string->symbol procedure, which is used to convert a string to a symbol, should be used with care, because it can be (mis)used to create symbols that cannot be accessed by Scheme:

(string->symbol ";unreadable") => ;unreadable

Given the above definition of explode,

(explode 'foo) => (f o o)

A procedure that composes a new symbol from a list of single-character symbols is a bit harder to implement, because there is a bit of type-checking to do. It has to be done to make sure that the list passed to that procedure really consists of single-character symbols. The inverse procedure of explode is called implode. Here is its code:

(define (implode x)
  (letrec
    ((sym->char
       (lambda (x)
         (let ((str (symbol->string x)))
           (if (not (= (string-length str) 1))
               (bottom "bad symbol in implode")
               (string-ref str 0))))))
    (string->symbol
      (list->string (map sym->char x)))))

This procedure basically works like explode, but in reverse order. It first maps a procedure over x which converts the symbols in the list to chars. The resulting list is converted into a string, and the string into a symbol.

Type checking is performed in the local sym->char procedure which, as its name suggests, converts a symbol to a char. It first converts the given symbol into a string, binding the result to str. If str has not a length of one character, a type error has occurred and the procedure reduces to bottom. If the string has a length of one character, this character is extracted using string-ref. (The first character of a string is at position zero, that is why zero is passed to string-ref.)

Using this definition of implode:

(implode '(f o o)) => foo
(implode '(f oo))  => bottom ; bad symbol in implode

2.5.1 Arithmetics with Lists

This little digression introduces two type conversion procedures that are not part of Scheme: int->list and list->int. These two procedures show how bignum arithmetics can be performed in terms of single digits.

The int->list procedure converts an integer number into a list of digits:

(define (int->list x)
  (letrec
    ((convert
       (lambda (in out)
         (if (zero? in)
             out
             (convert (quotient in 10)
                      (cons (remainder in 10) out))))))
    (if (zero? x) '(0) (convert x '()))))

Lists of digits open the way to a simple and portable (although inefficient) method of performing bignum arithmetics. Of course, it is not normally done in this way, but the the approach illustrates the fundamental principles of arithmetics with arbitrary precision. Here is a procedure that adds two lists of digits:

(define (add a b)
  (letrec
    ((result
       (lambda (a b c)
         (if (> (+ a b c) 9)
             (- (+ a b c) 10)
             (+ a b c))))
     (carry
       (lambda (a b c)
         (if (> (+ a b c) 9) 1 0)))
     (add2c
       (lambda (a b r c)
         (cond ((null? a)
             (if (null? b)
                 (cons c r)
                 (add2c '()
                        (cdr b)
                        (cons (result 0 (car b) c) r)
                        (carry 0 (car b) c))))
           ((null? b)
             (add2c (cdr a)
                    '()
                    (cons (result (car a) 0 c) r)
                    (carry (car a) 0 c)))
           (else (add2c (cdr a)
                        (cdr b)
                        (cons (result (car a) (car b) c) r)
                        (carry (car a) (car b) c)))))))
    (let ((r (add2c (reverse a) (reverse b) '() 0)))
      (if (= (car r) 0) (cdr r) r))))

The details of the add procedure are not very interesting. It uses the algorithm which most people use for adding numbers on a sheet of paper. Feel free to explore it on your own. The procedure can indeed operate on numbers of any size:

(add '(9 9 9 9 9 9 9 9 9 0) '(1 2))
=> (1 0 0 0 0 0 0 0 0 0 2)

List->int implements the reverse function of int->list. It converts a list of digits to an integer:

(define (list->int x)
  (letrec
    ((convert
       (lambda (in out)
         (if (null? in)
             out
             (convert (cdr in)
                      (+ (car in) (* 10 out)))))))
    (convert x 0)))

Using int->list, list->int, and add, you can add arbitrarily large numbers without using +:

(list->int (add (int->list 1234567890)
                (int->list 9876543210)))
=> 11111111100

Of course, add is a rather low-level procedure and all it can do is add natural numbers, not even integers. Implementing integer arithmetics and some more interesting procedures performing operations like integer addition, subtraction, multiplication, and exponentation is left as an exercise to the reader. Interestingly, the lowest-level operations are also the most complex ones. Writing a procedure that performs integer exponentation is a rather simple task compared to the implementation of add.