Scheme for Pythonistas
« Wednesday, October 23, 2013 »

python Scheme

Scheme might be scary at first by the heavy use of parens. It's not that bad and I'd say that it really depends on how you write your code. If your code ends with a lot of closing parens, then you might be doing something wrong and refactoring the code could reduce the amount of parens.

Defining variables.

In python, we usually use the = operator to affect a value to a variable. At the same time, the variable will get created in the local scope or affect the value to a globally scoped variable in some other cases. In Scheme, it works almost exactly the same way.

Python:

1
2
3
4
5
6
7
8
9
1. num = 2
2. string = "Dog"
3. list = [1 2 3 4 5]
4. AssociativeList = [[1, "Allo"], [2, "Fun"]]
5. HashTable = dict()
6. HashTable = dict(AssociativeList)
# Syntax sugar
7. HashTable2 = dict([[1, "One"], [2, "Two"]]) == {1: "One", 2: "Two"}
8. complex__number = 4+3j

Scheme:

1
2
3
4
5
6
7
8
1. (define num 2)
2. (define string "Dog")
3. (define list '(1 2 3 4 5))
4. (define AssociativeList '((1 . "Allo") (2 . "Fun")))
5. (define HashTable (make-hash-table))
6. (define HashTable (alist->hash-table AssociativeList))
7. (define HashTable2 (alist->hash-table '((1 . "One") (2 . "Two"))))
8. (define complex_number 4+3i)

It's clear to understand that the define function is affecting a value of name in the first parameter to the current scope. In fact, define may behave just like set! in some case which bind a value to the symbol in the first parameter. But latter about that.

Basic operations

In python and many other languages, people are used to write code using the operator syntax. The operator syntax is the normal way of writing code for that reason and people are used to it. It's probably because it is also the same syntax we used at school for a very long time while doing maths. Scheme like many other functional languages used the infix syntax. The first thing in a list is the operator that will behave on the other direct element of the list.

For example:

Python:

1
2
3
4
1. 2 + 3 + 4
2. 1 * 2 * 3
3. 2 + 3 * 4
4. 4 / 2 + 4 * 6

Scheme:

1
2
3
4
1. (+ 2 3 4)
2. (* 1 2 3)
3. (+ 2 (* 3 4))
4. (+ (/ 4 2) (* 4 6))

It should be pretty much clear that in scheme, we aren't calling operator on object but functions that receives a list of parameter and does something on them. The “+” can be used pretty much like the sum in python. So writing (+ 1 2 3 4) is pretty similar to sum([1 2 3 4]). We could then write a function mult that receives a list of number to multiply. What is important to understand is that the prefix syntax force the order of operation. The code at line 3 cannot sum 2 with the rest of the expression until the multiplication function doesn't return a number. For that reason, the code written with a prefix syntax like scheme is less likely to be ambiguous.

In python and other languages, one clever programmer has to understand the order of operation. For example, multiplication and division are executed first then substraction and addition. Operator on the same level order are executed from left to right. In scheme, it should evaluate from left two right each parameter recursively. Once each parameter of a function call are evaluated, it passes them to the function.

Here is a simple example:

Step 1

1
2
3
4
5
6
7
(+ (* 1
      3
      (- 4 2)
      (+ 4 6))
   3
   4
   (- 4 2))

Step 2

1
2
3
4
5
6
7
(+ (* 1
      3
      2
      (+ 4 6))
   3
   4
   (- 4 2))

Step 3

1
2
3
4
5
6
7
(+ (* 1
      3
      2
      10)
   3
   4
   (- 4 2))

Step 4

1
2
3
4
(+ 60
   3
   4
   (- 4 2))

Step 5

1
2
(+ 60 3 4 2)
=> 69

Usual operator for numbers will also work in scheme most of the time. Actually, in scheme operators are actually function that are named with the chars: +,-,*… There is no actual operator as in Python. In python, operator can be defined using the special functions __plus__ but in scheme, it doesn't exactly work like that.

Operator overloading is generally a bad idea unless you're developing something that is working with numbers or has some kind of mathematical meaning. It doesn't make much sense to have an object Dog with an operator /. It would be pretty hard to understand what the following snippet means: res = Dog("Mathew") / Dog("Barney"). I believe that operator overloading is good at some extent but in Scheme, we don't have operators and we don't have that problem either.

If we wanted the function / in ptyhon to do something particular with two dogs. We'd have to create static method. In scheme, we don't have the choice. So we create a function that takes 2 dogs and return something… This lead us to defining functions.

Functions

In Python, you might be familiar with lambdas. Lambdas are function like object that can be sent as parameter, they can be defined and affected directly to a variable or parameter position. They are quite useful to write small and concise code. Lambdas are unfortunately limited to one expression and aren't fit to write long piece of code.

1
2
3
lamb = lambda x,y: x+y
SortElements(elements, lamb)
SortElements(elements, lambda x,y: x<y)

In Scheme, each function is a lambda expression. The following code is similar to the python code written above. You might also notice that tests like <, > are also functions returning boolean values.

1
2
3
(define lamb (lambda (x y) (+ x y)))
(SortElements elements lamb)
(SortElements elements (lambda (x y) (< x y)))

Lambdas are created like this:

1
(lambda variables body ...)

Just like in python, lambdas are anonymous functions. The signature of the function, is like a list and values are binded to parameters in the order in which they are called. To make it easier, there is the special syntax for define which create named lambdas that can be called later on. It is pretty similar to python.

Our first function

1
2
def hello():
    print "Hello"
1
2
(define (hello)
  (print "hello"))

Function with parameter

1
2
def hello(world):
    print "hello ", world
1
2
(define (hello world)
  (print "Hello " world))

Parameters with a twist

1
2
def many_hello(what, *args):
    print args
1
2
3
4
5
6
7
(define (many_hello what . args)
  (print args))

; Similar to

(define many_hello (lambda (what . args)
  (print args)))

With the . operator, we can tell scheme to bind all remaining parameters to args. If that function is called with (many_hello 1 2 3 4). The variable what will receive 1 and args '(1 2 3). Keyword arguments are also possible but may be later.

One important thing to remember is that unlike python, the functions are always returning the latest thing that got evaluated. Consider the following piece of code.

1
2
3
4
5
6
7
8
def foo(x, y, z):
    if x < y:
        return z

    if y < z: 
        return x

    return x + y + z

This function has 3 possible ways to exit. It can branch to 3 different place. We could rewrite the above function like this to understand how it actually works.

1
2
3
4
5
6
7
def foo(x, y, z):
    if x < y:
        return z
    elif y < z:
        return x
    else:
        return x + y + z

In Scheme, we could literraly translate the code to this:

1
2
3
4
5
6
(define (foo x y z)
    (if (< x y)
        z
        (if (< y z)
            x
            (+ x y z))))

As you can see, to make the code return z, we have to make sure that it is the last possible thing to execute in the function. When there is nothing more to do, it returns with the last thing it saw. If we fail the first test, we fall in the second if and either choice will return a value. The if statement can be defined as such: (if condition true_expression false_expression). Yet nothing complicated but I'm sure it might look scary at first.

I'll finish with recursion for today. I assume that the reader knows what is recursion and how to use recursion to solve problems. In scheme, any kind of loop is achieved using recursion. Unlike other languages, scheme requires implemtors to implement tail recusion. Tail recursion allows recursive algorithm to work iterativelly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
(define (loop start stop)
  (print start)
  (if (< start stop)
    (loop (+ start 1) stop)))


(loop 1 4)
> 1
> 2
> 3
> 4

Since the call to loop is the last possible statement, it can replace the parameter with the one sent during the function call and jump to the top of the function without keeping traces of the old variables. This is a recurive iterative program. In some case, it might be also possible to write recurive program which will have to keep memory of the old calls. I believe the following version of the code above wouldn't be tail recurive.

1
2
3
4
5
(define (loop start stop)
  (print start)
  (if (< start stop)
    (+ 1 (loop (+ start 1) stop))
    0))

The last level of recursion will return 0 and each function will have its returned value summed to 1. This algorithm could be rewritten again to be recursive iterative.

1
2
3
4
5
(define (loop start stop level)
  (print start)
  (if (< start stop)
    (loop (+ start 1) stop (+ 1 level))
    level))

And to keep the old function signature:

1
2
3
4
5
6
7
8
(define (loop start stop)
  (let loopInner ((start start)
                  (stop stop)
                  (level 0))
    (print start)
    (if (< start stop)
      (loopInner (+ start 1) stop (+ 1 level))
      level))

In python we would have something like this, but it's not certain that python can handle tail recursive calls.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def loop(start, stop):
    def loopInner(start, stop, level):
        print start

        if start < stop:
            return loopInner(start + 1, stop, level + 1)
        else:
            return level

    return loopInner(start, stop, 0)

I hope it will help someone one day. If you have any question or comment, feel free to comment or to leave me a message on my email. I've been playing with Scheme for a little while and that is how I feel about scheme coming from a Python background. I think both languages are much closer than one might think.

comments powered by Disqus

Copyright © 2015 Loïc Faure-Lacroix