The Racket Language
Contents
The Racket Language¶
Racket is a Function Programming Language. It can be downloaded for free from https://racket-lang.org.
Most programmers learn Object Oriented Programming Languages or Imperative Programming Languages first. Languages like C++, Python, and Java are all Object Oriented Languages. C is an Imperative Language, it has most of the same features but no classes.
These languages use a combination of control structures, objects, and functions to build complex programs. Functional Programming Languages focused on functions. Some modern functional languages have a loops and objects added to a limited extent. They are a different way to think about programming. Depending on the problem, one type of language may make it easier to solve a problem.
Functional Programming is built on a theory call the Lambda Calculus developed in the 1930s [Wikipediacontributors21b]. The first functional programming language (IPL) was developed in 1956 [Wikipediacontributors21b]. We will be using Racket, a modern version of LISP. LISP was originally developed in the late 1950s [Wikipediacontributors21b].
Functional programming language allow us to focus on specific areas of computation. By limiting the tools of our programming language, we can examine how they work at a deeper level. This will also limit the number of rules needed to prove statements about programs. Making it easier to verify their correctness.
The Lambda Calculus is Turing Complete [Wikipediacontributors21d]. This means anything you can write in any other language can be written in it. You might need to find more clever solutions, but the language is not limited in what it can do. The theoretical underpinnings of Racket and the Lambda Calculus will be covered in a later section.
Functional Notation¶
The following code is written in Python. There are many cases of special syntax and rules in python the programmer has to remember.
def f(x,y):
return x+y
a=0
b=2
while a < 10:
print(f(a,b))
a+=2
b+=1
print("The End!")
This code has a mix of prefix functions calls (f(a,b)) and infix calls (x+y). The addition symbol is written using infix notation. It takes two inputs, but they appear on either side of the operator. The print command uses prefix notation. It appear before the inputs. The return command is also a function, but it doesn’t use parenthesis because it is a special case. The while command has its on special format using tabs and colons.
If we needed to write out every rule about the syntax of the Python language, it would not be easy. Then stating properties of what happens when these commands interact becomes even more overwhelming.
Racket uses one primary pattern for all commands.
(function_name input1 input2 input3 ...)
Every command starts and ends with a set of parenthesis. The first thing within the parenthesis is the function name. Any other item within the parenthesis is an input to the function. Distinct items within the parenthesis are separated by spaces.
All the basic math operations will follow the same pattern as any other function. Why should they be special? They are just functions.
A few common functions are show in the table below.
Description |
Classic Notation |
Racket |
|---|---|---|
Addition |
\(5+3\) |
|
Subtraction |
\(5-4\) |
|
Multiplication |
\(2 * 4\) |
|
Division |
\(2/3\) |
|
Greater Than |
\(10 > 7\) |
|
Less Than |
\(9 < 1\) |
|
Equal to |
\(9=1\) |
|
This many seem annoying and it will take a little while to get used to. We will see some interesting advantages to this method. Knowing that every function always has the same pattern will be a significant advantage. We won’t have to worry about any odd special cases.
The conditional statement (if) is a fundamental feature of most languages. It almost always has some special syntax. The following Python code uses a few different forms of conditionals.
if 1 > 3:
a=5
if 2 < 7:
b=2
else:
c=9
Why is the if statement special? Since Python has variables, objects, and more, there are many things that can happen during the execution of the conditional.
In a functional language, there are only functions, inputs, and outputs (return values). The conditional idea can be simplified. A conditional is a function that returns one of two values based on its input.
(if A B C)
The if statement always does the same thing
If A is True return B
If A is False return C
The if statement must always have exactly three inputs.
We can now write slightly more complicated code.
(if (> 7 6) 9 2)
Executing this command will return 9.
This does a calculation, but doesn’t really let us program yet. How do we store a result for later computation? How do we write code with variables? We need to be able to define our own functions.
Defining Functions¶
To solve any significant problems, we need to define our own functions.
The define command allows us to create new functions. It follows the functional programming pattern.
(define (function template) (function body) )
We can create a simple function to square a number.
(define (f a) (* a a))
This command says we are defining a function. The name of the function is f. It takes one input parameter named a. When the function is called execute and return (* a a). There is no explicit return command in Racket because every command must return something. All values are passed by either function inputs or function returns.
Once the function is created, we can call it. Again the pattern starts with a parenthesis then the function name.
(f 10)
This code returns \(100\). The full code for the file is shown below. Notice the first line denoting the programming language. This is required by the Racket IDE.
#lang racket
(define (f a) (* a a))
(f 10)
There are two features of programming languages you may have noticed haven’t been introduced. They are variables and loops. These don’t exist in pure functional languages. Racket is not a pure functional language, so there exist a kind of loop and variable. Our goal is to study pure functional languages. These commands do not exists for us.
You can define a constant in Racket.
(define X 5)
Don’t expect to be able to freely change this like a variable. It is a constant. We can delete it and replace it with another constant, but this can cause problems. These constants are not as flexible as variables in an imperative language.
Recursive Design¶
If we don’t have loops, there is only one way to create repetition. We need to use recursion! Recursion is the only way to iterate in a purely functional language.
Let’s say we want to make a function to multiply two numbers. Obviously a function for this is built in, but we will use it as an example.
I want to create a function such that (myMult a b) returns \(a*b\).
First, lets start with a example to work through.
\( \begin{align} 5*2=10 \end{align} \)
This function has two inputs \(5\) and \(2\). We need to figure out a way to define in recursively. Specifically we want to define multiplication in terms of multiplication of smaller values.
What is the smallest multiplication we can do? Assuming only positive numbers for now, we can do \(a*0=0\). Any number times \(0\) is always each to zero. It doesn’t matter what number it is, this is always true.
This provides us with a base case. A base case is the part of a recursive function that does not have a recursive call. It is a situation where we can directly compute the answer. A function can have many base cases. It must have at least 1 base case or the function will enter an infinite loop.
What does \(5 * 2\) mean recursively? What is a smaller multiplication? There are two ways to write \(5 * 2\) in terms of smaller multiplications.
\( \begin{align} 5*2 =& 5+5*1 \\ 5*2 =& 2+4*2 \end{align} \)
In both cases, the right side of the equation is a simpler multiplication than the left side. Since we picked \(a * 0\) as our base case, we will pick \(5 + 5 * 1\) as the smaller recursive definition. This way we are consistently changing the \(b\) input.
Let’s try and write out that idea more algebraically.
\( \begin{align} a*0 =& 0 \\ a*b =& a+a*(b-1) \end{align} \)
Notice that the value of \(b\) gets consistently smaller until it reaches 0. If we want a recursive call to end, it needs to get smaller in some way. The easiest way is to literally decrease the value. We will see many other definitions of smaller in later sections.
We can put the pieces together and write a function in Racket.
#lang racket
(define (myMult a b)
(if (= b 0) 0 (+ a (myMult a (- b 1))))
)
(myMult 5 2)
What happens when we run our code? The Racket comment symbol is a semi-colon. This means if you accidentally end your line in a C style semi-colon, it just makes a comment!
(myMult 5 2) ;Original Call
(if (= 0 2) 0 (+ 5 (myMult 5 (- 2 1)))) ;Apply Definition of the Function
(+ 5 (myMult 5 1)) ;First Recursive Call
(+ 5 (if (= 0 1) 0 (+ 5 (myMult 5 (- 1 1))))) ;Apply Definition of Function
(+ 5 (+ 5 (myMult 5 0))) ;Second Recursive Call
(+ 5 (+ 5 (if (= 0 0) 0 (myMult 5 (- 0 1))))) ;Apply Definition of Function
(+ 5 (+ 5 0)) ; Final Result 10
Walking through a function like this is called Equational Reasoning. Equational Reasoning is a formal method for walking through how functions execute. It will be introduced in a later section. The previous example would not be formally correct, but gets the idea of the function’s execute across.
Debugging recursive programs can be hard. There are a few tricks in Racket to make it easier. The begin command allows you to execute multiple statements but only return the last value. The display command lets you print things. Using these two commands together, we can add print statements without changing our code. We just need to add them before the statement, since the last line will actually be returned. The newline command prints a newline.
The debugging version of our function is show below.
#lang racket
(define (myMult_debug a b)
(begin
(display "(myMult_debug ")
(display a)
(display " ")
(display b)
(display ")")
(newline)
(if (= b 0) 0 (+ a (myMult_debug a (- b 1))))
)
)
(myMult_debug 5 2)
When the code is executed, the printout is shown below.
(myMult_debug 5 2)
(myMult_debug 5 1)
(myMult_debug 5 0)
10
Lines 1-3 will be printed in a different color by DrRacket. This tells you that the values are only being displayed. They are not return values and cannot be used.