Scheme Crash Course

This crash course on Scheme that I'm writing is the kind of course that I would had liked before starting to read SICP. This crash course is geared towards people who are already familiar with some programming language and want to start with SICP but are not really comfortable Scheme or any LISP for that matter. All the Python code in this blog is Python 3 compatible and all the Scheme code is MIT-Scheme compatible.

The whole blog post is written in such a way that you should be able to pick up Scheme in an hour or so by typing out the programs in an online Scheme interpreter and see how the things work there. The examples here are in two languages namely Python and obviously Scheme. Every concept here is first introduced in Python and then a exact implementaion is shown in Scheme. The main reason for choosing Python is that it is very easy and looks a lot like pseudocode and for those who don't know the language can easily undrstand the code.

Arithematic operations

Since Scheme is a LISP it does not have operators that we can use in a infix notation, so we have operators like +, -, *, / which have to be used in prefix notation. To make this easier let's visualize these operators to be nothing but functions, which they actually are and makes much more sense when think them to be like that.

We will therefore assume that the languages that we are comparing Scheme do not have arithematic operators but have functions like add(), subtract(), multiply(), divide(). Let's start writing some of these arithematic operators in Python. After the Python block of the code the exact Scheme version of the same will be shown in the block below it.

# (1 + 2) * (5 - 3) / 9
divide(multiply(add(1, 2), subtract(5, 3)), 9)  # => 0.666666666666666

# 3 + 4 + 5 + 6 + 8
add(3, 4, 5, 6, 8)  # => 26

# 9 * 9 - 3 - 5 - 3
subtract(multiply(9, 9), 3, 5, 3)  # => 70

# zero arguments
add()  # => 0
; (1 + 2) * (5 - 3) / 9
(/ (* (+ 1 2) (- 5 3)) 9)  ; => Value: 2/3

; 3 + 4 + 5 + 6 + 8
(+ 3 4 5 6 8)  ; => Value: 26 

; 9 * 9 - 3 - 5 - 3
(- (* 9 9) 3 5 3) ; => Value: 70

# zero arguments
(+)  # => 0

Let's first try to understand the above code. The Python part of the code has these functions add(), subtract(), multiply(), divide(). There functions take any number of arguments on which the respective operation is to be recursively performed. For exaple in subtract() the first argument will be taken and one after the other all the remaining arguments of subtract() will be subtracted from till ultimately just one value is left. In case if no arguments are passed then a 0 will be returned.

Now let's try to understand the Scheme code. Scheme is a typical LISP so every function call is enclosed in parenthesis. All the arguments passed to the function are separated with spaces. The first argument or the word that follows just after ( is the call to that function. For eample in (+ 2 3), + is the function call to add and 2 and 3 are the arguments passed to that add function.

Variables

# define a variable MAX that holds 500
> MAX = 500
> MAX  # => 500

# define a constant PI that returns the value of PI
> PI = 3.14
> PI  # => 3.14

# compute sum of two numbers and store it in a variable
> SUM = 3 + 6
> SUM  # => 9
; define a variable MAX that holds 500
> (define max 500)
> max  ; => Value: 500

; define a constant PI that returns the value of PI
> (define pi 3.14)
> pi  ; => Value: 3.14

; compute sum of two numbers and store it in a variable
> (define sum (+ 3 6))
> sum  ; => Value: 9

Let's now look at these above things as variables, but name value binding. What exactly do we mean by name value binding? Simply stating it's that when we enter that name, it is evaluated to it's respective value that it was assigned to. This name can be later changed in the code be reassigning another value to that variable. To prevent that, we should take care about the kind of name that we give to the variables. Naming should be such that we do not reassign that name to something else. In other words even though the so called variables are not constant they should be treated as such or else they will not maintain referential transparency.

The syntax for defining a variable is very easy. Take the example of PI (define PI 3.14). Whatever follows define is a new name with which we are associating a value, PI in this case is the name and 3.14 is the value associated with it. That is simply how assigning variables work in Scheme. The we can also evaluate an expression as a value assigned to name, this is done for sum in the code snippet shown above.

Functions

# Lambda implementation of square function
> square = lambda x: x * x
> square(7)   #  => 49

# Square implementation as function (syntactic sugar)
> def square(x):
      return x * x
> square(7)
;  Lambda implementation of square function
> (define square (lambda (x) (* x x)))
> (square 7)  ;  => Value: 49

; Square implementation as function (syntactic sugar)
> (define (square x) (* x x))
> (square 7)  ;  => Value: 49

By default in Scheme we define variable of which the value is lambda which is first shown in Python. In Python this is not the default way we define a function. But this is again written in that way because that's how it is done in Scheme. The second function that shows default way of implementing functions in Python. The same is shown in Scheme which is nothing but syntactic sugar for binding lambdas to name.

Taking a decision

# Old enough to drink string
def old_enough(age):
    if age >= 18:
        return "Yes"
    else:
        return "No"

old_enough(34)
old_enough(17)

# Check if a given number is even returns the respective string
def is_even(number):
    if number % 2 == 0:
        return "Yes"
    else:
        return "No"

is_even(2)
is_even(3)
; old enough to drink string
> (define (old-enough age) 
          (if (>= age 18) "Yes" "No"))
> (old-enough 34)  ;  =>  Value: "Yes"
> (old-enough 17)  ;  =>  Value: "No"

; Check if a given number is even returns the respective string
> (define (is-even number) (if (= 0 (remainder number 2)) "Yes" "No"))
> (is-even 2)  ;  =>  Value: "Yes"
> (is-even 3)  ;  =>  Value: "No"

List: Getting length

# Recursively iterating to get the length of the list
def length_of_list(lst, current_length=0):
    if lst == []:
        return current_length
    return length_of_list(lst[1:], current_length+1)
; recursively iterating to get the length of the list

List: Concatenating two lists

# Simply concatenating two lists
[1, 2, 3, 4] + [5, 6, 7]

[1, 2, 3, 4, 5, 6, 7]
; Simply concatenating two lists (cons)

List: Appending element to list

# Simply appending element to list
[1, 2, 3, 4, 5].append(6)
; Simply appending element to list

List: Getting the first element in the list

[1, 2, 3, 4, 5][0]

List: Getting the rest in the list

[1, 2, 3, 4, 5][1:]


List: Reversing

# Recursively iterating to reverse the list
def reverse_list(lst, new_lst=[]):
    if lst == []:
        return new_lst
    return reverse_list(lst[1:], list(lst[1]) + new_lst)

# Use the reverse function provided by the language
> list(reversed([1, 2, 3, 4, 5]))  # => [5, 4, 3, 2, 1]
; recursively iterating to reverse the list (use car, cdr and cons)

; Use the reverse function provided by the language

Compute factorial


def factorial(number, current_product=1):
    if number == 1:
        return current_product
    return factorial(number-1, current_product * number)


Compute fibonacci


def fibonacci(count, current_list=[], previous=0, current=1):
    if len(current_list) == count:
        return current_list
    return fibonacci(count, current_list.append(previous), previous=current, current=previous+current)


Find element in the list

def search_element(lst, key, index=0):
    if index == len(lst):
        return None
    if lst[index] == key:
        return index
    return search_element(lst, key, index+1)


Simple input and output


int(input()) + 45 # input an int and add 45 to it

print("Enter your name: ")
"Hello " + input() # output a prompt and take string input name and say hello



Writing tests



(load "test-manager/load.scm")
(load "src/ex_1.2.scm")

(in-test-group
  translation-of-an-expression-into-prefix-form
  (define-test (expression-infix)
     (assert-= (expression) -37/150)))
(run-registered-tests)