Recurse.se Yada yada on Software Development

12Jan/120

A Functional Language

This entry is part 2 of 5 in the series Towards Functional Programming

In this post I show the basics of the language Scheme, in order to be able to use Scheme in later posts to prove a few points on functional programming as a useful and powerful paradigm. Scheme is chosen for it’s simple syntax and minimalistic design.

Choice of language

I decided to start my journey towards understanding functional using F#, a new functional programming language from Microsoft. This was because it seemed like the perfect choice for someone like me who knew C# and the .NET Framework, as you can use .NET Framework classes from within F#, as well as easily call your F# code from C#, and vice versa. But I quickly began worrying that I wasn't doing it right, as F# is really a multi-paradigm language in which you can code in an imperative style, and I felt I was doing Frankenstein-style code (Frankencoding, if you will).

I therefore looked at other functional languages, that would not let me drift back into the imperative world so easily, with the intention of coming back to F# later. The weird looking syntax and terminology of Haskell really threw me off, and Erlang was also quite confusing. Lisp looked more promising, except for a bit of initial parenthesis angst, but it was when I learned more about Scheme, a beautifully minimalistic Lisp dialect, that I knew I’d found what I had been looking for!

Scheme schematics

I started toying with Scheme using PLT Scheme. (Since then that particular dialect of Scheme I’m using has been renamed Racket but it’s still “Scheme” for all our intents and purposes).

Key points about the Scheme language are:

  • Truly minimalistic design, meaning very few keywords and syntactic forms
  • Strongly but dynamically typed
  • Everything is either a value, or a list of values. The list is the primary data structure.
  • Functions are values too, and can be stored and passed around
  • As with all Lisp dialects, the code itself is list structured, as all statements are list-formed expressions
  • All statements are also expressions returning a value
  • All values are immutable (unchangeable), even lists
  • A powerful macro system for rewriting code at compile time

First let’s look at the syntax, and then we can elaborate on some of the other key points. The explanations of some things will have to wait until later posts, in order to keep this post to the point, but feel free to ask in the comments.

The Syntax of Scheme

This table summarizes most of what you need to know about Scheme syntax:

Concept Syntactic form Examples
Identifier ‹id› convert
bigger?
append-name
pos
Definitions ( define ‹id› ‹expr› )

Binds the identifier ‹id› to the value of the provided expression.

(define num 42)
(define powers (list 1 2 4 8 16))
Conditionals ( if ‹expr1› ‹expr2› ‹expr3› )

if expr1 is true, evaluates expr2 otherwise evaluates expr3

(if (empty? lst)
    (min num lower-bound)
    (max num upper-bound))
Local bindings ( let ([‹id› ‹expr›]) ‹body-expr› )

Binds one or more identifiers to the value of the provided expressions. The identifiers are visible only inside the body-expr.

(let ([a (random 10)]
        [b (random 10)])
   (if (> a b)
       "A was bigger than B"
       "B was bigger than A"))
 
Function calls ( ‹id› ‹expr›* )

When ‹id› is bound to a function, invokes that function with the value of the remaining expressions as parameters

(write-log "num is ~a now" num)
(sum 2 8 5 6) 
(multiply 2 (sum num 1))
(exit)
Function definition syntax ( define ( ‹id› ‹id›* ) ‹body-expr› )
binds the first id to a function which takes parameters named by the remaining ids, and the body-expr as the implementation
(define (max a b)
          (if (> a b) a b))
Anonymous functions ( lambda ( ‹id›* ) ‹body-expr› )

creates an unnamed function which takes parameters named by the ids, and the body-expr as the implementation

(lambda (a b) (if (> a b) a b))

And, yes, I’m skimming over some parts, but this will get you a long way. All these are also expressions in their own right - with the exception of the define form which returns no useful value - which means you can do something like in this silly example:

(define min/max (let ([num 3])
                  (if (negative? num) 
                      (lambda (a b) (if (> a b) a b)) 
                      (lambda (a b) (if (> a b) b a)))))

where min/max is defined as either a function returning the minimum of two values, or another function returning the maximum of two values, depending on the sign of num (and num is not visible outside the let). Note that whitespace and indentation is not significant in Scheme.

No operators, but there are always functions

You are probably used to writing expressions such as 1 + 2 * 3 * 4 + 5 / 6. where “operators” like + and * are “infix” (placed in the middle), between two sub-expressions.

In Scheme there’s no infix operators, as these operators are instead ordinary functions, and thus written in prefix form (placed in the beginning) just like any other function call in Scheme. The above expression then becomes;

(add 1 (multiply 2 3 4) (divide 5 6))

Or, rather, since the add, multiply and divide functions is actually named +, * and / (which are all perfectly valid Scheme identifier names), it actually becomes:

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

Yes, this feels awkward when you are used to the traditional way of writing expressions, but there are compelling reasons. This rule makes the syntax far more regular, if nothing else. And you may freely store and pass around these functions, just like any other value or function. In C#, even though you can pass around functions nowadays, you still cannot pass around the operators as if they were functions.

Note that prefix arithmetic like the above is a property of Lisp-like languages like Scheme, and has absolutely nothing to do with functional programming per se. So don’t write off FP just because prefix arithmetic at first glance seems like the dumbest thing since 7-bit ASCII!

Comparison operators are also functions

Using the same logic, comparison operators like ‘and’, ‘or’, <, >, and = are also functions, so you would write:

(or (and (> a 0) (< b 0)) (= a b 10))

instead of say (a > 0 && b < 0) || (a == 10 && b == 10) in C# or Java. (Note that and/or are really “special forms”, as they short circuit, and returns the last value that needed to be evaluated in order to determine the result)

Now I think you know enough Scheme to get your feet wet! Let’s fool around with it in the next post.

Series Navigation<< A Paradigm ShiftFun with Functions >>
Tagged as: Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

No trackbacks yet.