Scheme Crash Course

Sep 18, 2018 - 7 min read - 1357 words

Tanay PrabhuDesai

[Software|Data] Engineer 👨‍💻 and loves Science 🧪, Space and universe 🪐, Philosophy 🧘‍♂️

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 <code>subtract()</code> the first argument will be taken and one after the other all the remaining arguments of <code>subtract()</code> 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"

Now we have to decide if the age of the person which is entered is of legal drinking age of not. Since we’re comparing with a functional language, let’s do it in Python the way we would do it in Scheme. So we define a function called is_even() and we pass the age to it. Inside the function has an if statement that returns the string which is either "Yes" or "No" depending on if he is legal or not. The Scheme version of this looks very similar in which if is the function call of which the first argument is an expression that evaluates to a boolean value. Where it (>= age 18) checks if age is greater than 18 or not. If the expression evaluates to <code>lol</code>

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
(define (length-of-list lst current-length)
  (if (null? lst)
      current-length
      (length-of-list (cdr lst) (+ current-length 1))))

; usage example
(length-of-list '(1 2 3 4 5) 0) ; => Value: 5

The problem the above code solves is finding the length of the list that passed to the length-of-list function. In addition to that we are also introduced to recursion in the context of lists. Instead of using a built-in length function, we recursively traverse the list and count elements one by one. This helps build an intuition of how list iteration and base cases work in Scheme.

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 (append)
(append '(1 2 3 4) '(5 6 7)) ; => Value: (1 2 3 4 5 6 7)

Here, we see how to combine two lists into one. In Python, this is done with +, while in Scheme, we use the append function. This example above showcases Scheme’s functional style where list operations are explicit and declarative.

List: Appending element to list

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

; Simply appending element to list
(append '(1 2 3 4 5) '(6)) ; => Value: (1 2 3 4 5 6)

Appending a single element in Scheme is also done using append, but the new element must be wrapped in a list using (list x) or '(x) because append expects lists. This emphasizes the distinction between atoms and lists in Scheme.

List: Getting the first element in the list

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

; Getting the first element of the list
(car '(1 2 3 4 5)) ; => Value: 1

To access the first item of a list in Scheme, we use car. This mirrors Python’s list indexing with [0]. The function car stands for “contents of the address part of register”—a historical name from early LISP machines.

List: Getting the rest in the list

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

; Getting the rest of the list after the first element
(cdr '(1 2 3 4 5)) ; => Value: (2 3 4 5)

The counterpart to car is cdr, which returns the remainder of the list after removing the first element. This is similar to Python’s slicing: lst[1:]. These two functions are essential to understanding list processing in Scheme.

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
(define (reverse-list lst new-lst)
  (if (null? lst)
      new-lst
      (reverse-list (cdr lst) (cons (car lst) new-lst))))

; usage
(reverse-list '(1 2 3 4 5) '()) ; => Value: (5 4 3 2 1)

; Use the reverse function provided by the language
(reverse '(1 2 3 4 5)) ; => Value: (5 4 3 2 1)

This example demonstrates two ways to reverse a list: one with a custom recursive implementation and another using the built-in reverse function. The recursive approach reinforces how you can use car, cdr, and cons to build new lists.

Compute factorial

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

; tail recursive factorial
(define (factorial number current-product)
  (if (= number 1)
      current-product
      (factorial (- number 1) (* current-product number))))

; usage
(factorial 5 1) ; => Value: 120

Here, we implement a tail-recursive factorial function, which accumulates the product as we recurse down. This introduces the concept of tail recursion—a style of writing recursive functions where the recursive call is the last action performed.

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)

; helper function for tail-recursive fibonacci
(define (fibonacci count current-list previous current)
  (if (= (length current-list) count)
      current-list
      (fibonacci count
                 (append current-list (list previous))
                 current
                 (+ previous current))))

; usage
(fibonacci 6 '() 0 1) ; => Value: (0 1 1 2 3 5)

Fibonacci in this case is implemented using tail recursion with an accumulator list. The function progressively builds up the list of numbers, giving a more efficient version compared to naive recursive implementations. It’s a great example of functional iteration.

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)

(define (search-element lst key index)
  (cond ((null? lst) #f)
        ((= (car lst) key) index)
        (else (search-element (cdr lst) key (+ index 1)))))

; usage
(search-element '(1 2 3 4 5) 4 0) ; => Value: 3
(search-element '(1 2 3 4 5) 9 0) ; => Value: #f

This recursive function searches for an element in a list and returns its index. It demonstrates how to use cond for branching and how to perform comparisons and recursive traversal using car and cdr.

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

; input an int and add 45 to it
(+ (read) 45)

; prompt and greet user
(display "Enter your name: ")
(define name (read))
(string-append "Hello " name)

This section shows how to take user input and produce output in Scheme. We use (read) for input and (display) to print prompts. string-append is used to combine strings, mimicking Python’s input() and string concatenation (+) behavior.

Writing tests

# Python equivalent test using assert
def expression():
    return (1 + 2) * (5 - 3) / 9

assert abs(expression() - (-37/150)) < 1e-9  # placeholder value from scheme test

(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)

Testing in Scheme uses a test framework loaded via (load "test-manager/load.scm"). This section shows how to write unit tests using define-test and assert-=, helping you build testable Scheme programs, which is especially useful when working through SICP exercises.

Tags:

• scheme
• crash course
• programming
• sicp
• dr. racket

Arch Linux Broken Kernel Patch

SICP Challenge