Scheme for Pythonistas 2
« Sunday, October 27, 2013 »

python Scheme

Yesterday I wrote a small introduction to Scheme for Python programmers here. I believe it might be a good start because being new to Scheme myself is pretty much what I understood first. Today, I read some questions on Stackoverflow and felt that I had to keep going. With hopefully more and more complicated samples. I'll try to cover it this article some new basic stuff.

  • Branch statement (if, cond…)
  • use of set! and define
  • let expression to create local variables
  • named let to create loops
  • let* recursive to create interdependant variables

Branching statements

I have been programming for many years and only recently discovered that statements like if, switch, unless etc. could be called as branching statements because a program can be written as a tree or graph. A if is branching a program in at most two different places. If the condition is true, it execute the first statement. If the condition is false it may execute the second statement or keep going if there is no second statement. A if in Scheme can be written like this.

1
2
3
4
5
6
7
(if condition
    statement1
    statement2)

(if (> x y)
  x
  y)

In Scheme, the if statement will return the result of the statement it executes. As you can see, the last sample above is returning the maximal value.We can then rewrite it in a lambda that return the maximal value of 2 variables.

1
2
3
4
(define (max x y)
  (if (> x y)
    x
    y))

It as easy as it can be. Now what if we wanted the squared value of max(x, y)?

1
2
3
4
5
6
7
8
9
(define (maxSquared x y)
  (if (> x y)
    (* x x)
    (* y y)))

; A smarter way to write it
(define (maxSquared x y)
  (let ((max (if (> x y) x y)))
    (* max max)))

In the first sample above, you can see that we can not only return a value but execute a statement and return its value. In the second sample, I used the let block to reduce the complexity of the function. Since we are doing the same operation on the result of the if, it doesn't make sense to repeat the operation in each statement. We can instead store the result of the if in a variable named max and square the max.

In python we could write the above function like that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def maxSquared(x, y):

    if x < y:
        max = x
    else:
        max = y

    return max * max

# Or more simply
def maxSquared(x, y):
    max = x if x > y else y
    return max * max

Now that you should understand exactly how the if statement works, I'll go back to one example I wrote from the first article.

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
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, the scheme version isn't really sexy and nesting ifs can make the code harder to read than the code in Python. Fortunately Scheme has some other construct that we can play with. In this particular case, it makes more sense to use the cond function. We could then rewrite the above function like this:

1
2
3
4
(define (foo x y z)
  (cond ((< x y) z)
        ((< y z) x)
        (else (+ x y z))))

The cond function is pretty much similar to a switch/case statement. The cond function is called with lists of conditions paired with expressions. To make it easier to understand, here is an example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
(cond
  (condition1 expression1)
  (condition2 expression2 expression3)
  (condition3 expression4 expression5 ...)
  (conditionN expressionN ...))

# And

(cond
  (condition1 expression1)
  (condition2 expression2 expression3)
  (condition3 expression4 expression5 ...)
  (conditionN expressionN ...)
  (else expressions ....))

When evaluation cond it will test the first condition, if it fails, it will evaluate the next condition. As soon as a test test to true, it will execute the expressions that are related to the condition. Each condition are packed in their own list followed by expression that should be executed in order if the condition evaluates to true. The else that should be present as the last condition might be an implementation specific thing. In chicken scheme, trying to add conditions after a else will create a warning but is still possible.

1
2
3
4
5
6
; Define else as boolean true
(define else #t)

(cond
  (condition1 expr...)
  (else ...))

In chicken scheme, even if you define else to #f, it won't change how the else is handled. Also, it is important to note that the latest evaluated expression is the value returned by the cond statement. Which means that we can nest the cond statement just like a if. In fact, in functional languages, any function that doesn't have side effect should return something that can be later used somewhere else. The result of theses functions can be used directly as argument to other functions instead of creating variables. The good thing about it is that you're unlikely to see unused variable in functional code. We rarely have to create variables since we are probably going to call directly other function with the result of other functions.

The let expression

The let expression is one important expression, it allows us to create variables that can be used multiple times. Variables in let are limited to the length of the let. Variables are lexically scoped and destroyed with the let that created them. Let expressions are hidden lambdas.

1
2
3
4
5
; These are equivalent
((lambda (x y) (+ x y)) 1 2)

(let ((x 1) (y 2))
  (+ x y))

In python, there is nothing really similar. It's pretty much like creating a function and calling it directly after. Using the lambda syntax, we could write something like this:

1
2
# Almost like the first example of lambda
(lambda x, y: x + y)(1, 2)
1
2
3
4
# It's pretty much the only possible equivalent.
def plus(x, y):
    return x+y
plus(1, 2)

Unfortunately, python doesn't really handle anonymous function with more than one expression. Since let are usually unamed, it is hardly possible to reproduce in python with more than one expression. But there is more to let in Scheme. Since recursion is pretty much important and that using define and set! within functions might not be always a good idea. It is possible to create named let that can be called recursively from within.

In my first article, I used the named lambda to do recursion:

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

Use of define and set!

Since define and set! are lexically scoped and are pretty much the same thing as =. Someone could ask himself, what is the point of using let instead of define or set!. Well, I'd say that let are safer to use. Let's look at an example.

1
2
3
4
5
(define a 1)
(let ()
  (set! a 2)
  (define a 3)
  (set! a 4))

What will be the value of a after the execution? Think about it… If you think that after the execution the value of a should be 2 then you are right. To make it clear, here is how I believe thigns are happening.

  • We defined a in the current scope (global)
  • We entered the let
  • We set a to 2 (set is searching for a and found it in the global scope)
  • We define a in the current scope (let)
  • We set a to 4 (we found a in the current scope and we leave the global unchanged)
  • The let return and anything that was created inside it is also freed.

If we did write the code like this, the value of a would remain unchanged in the global scope.

1
2
3
4
5
(define a 1)
(let ((a 2))
    (set! a 2)
    (define a 3)
    (set! a 4))

The use of set! may be dangerous as it can change the state of a variable in a global scope. The define should always define local variables but if you use set! before defining a local variable, then you are playing with fire.

In python, in order to have access to a global variable, you have to mark it as global.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
a = 2

def hmm():
    a = 3

hmm()
a == 2
>>> True

def hmm():
    global a
    a = 3

a == 2
>>> False

# But in python, this is illegal
def hmm():
    a = 2
    global a
    a = 3

# also illegal
a = 4
def hmm():
    print a
    a = 3

In Python, we can read a global variable without marking it global as long as we aren't going to modify it. If we are assigning a value to a variable, it will get created locally and the global variable gets masked by the local variable. If we are assigning a value to a variable locally, any try to read a value from that variable before assignment will result into an unbound variable. In Scheme, as soon as something exists, we can use it. Once global variables are masked, we are stuck with local variables and global variables remain untouched.

Now more about the named let. It's like a usual let but with a name. The name can be used like a function call and the parameters are the same that we used to create it. Well we can change the parameter but they are in the same order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
(let for ((count 10))
    (print count)
    (if (> count 0)
      (for (- count 1))
      #t))


; Prints
> 10
> 9
> 8
> 7
> 6
> 5
> 4
> 3
> 2
> 1
> 0
returns #t

On each step, the variable sent in the position of count is decremented by one until it reaches 0. When it reaches 0 it will return #t and the recursion stops. The execution would then leave the let and keep going. Calling the function for outside of the let should not be possible unless the variable is already define in a different closure.

Recursive let

The let syntax does come in multiple flavour for better result. The recursive let is a special case that allows the programmer to use previously defined variables. This syntax is called let* instead of just let.

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(let* ((a 1)
       (b (+ a 1))
       (c (* a b)))
  (print a)
  (print b)
  (print c))

> 1
> 2
> 2

In python, I'd imagine this non working example:

1
2
3
4
5
6
def hmm(a=1, b=a+1, c=a*b):
    print a
    print b
    print c

hmm()

Unfortunately how the language is defined, it isn't possible to do. One would have to create 3 different variables and call a function like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def let():
    a = 1
    b = 1 + a
    c = a * b

    print a
    print b
    print c

let()

# Converting how the scheme code is built to python it would look like this
# But I'm pretty sure that how it is done internally is implementation specific
# and it could be done effectively
def let():
    def let2(a):
        def let3(b):
            def let4(c):
                print a
                print b
                print c
            return let4(a*b)
        return let3(a+1)
    return let2(1)

let() 

There are more let variant and It's still pretty new to me and It would take a long time to talk about them. The most important is to understand the basics and then the other form of let and lambda should be easy to learn. As I'm trying to compare languages to each others I won't go into details much more. What is less obvious is that the let form has some advantages over “usual” sequential programming. A let can be easily transformed to a named let. Named let can be then reused recursively. Arguments of the closure are defined together. In python, variable can be defined anywhere and it might cause confusion and unused variables. In Scheme, we know which variables are used and where they should be located. It might sound a bit like C where variable declaration had to be done first. In Scheme, it does feel natural because let block can be small or big. A function may contain multiple let blocks and they are self contained. I believe it forces programmers to write clean code. If Scheme code isn't clean… it will be quite evident and will look pretty ugly.

comments powered by Disqus

Copyright © 2015 Loïc Faure-Lacroix