« Return to index

HOP WPO 1

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

Section 0: Installing DrRacket

We will be using DrRacket throughout this course as the IDE for writing Scheme programs. DrRacket is available on the lab computers on both Windows, Mac and Linux.

If you are using your own machine you have to install DrRacket yourself.

  1. Download DrRacket from https://download.racket-lang.org/
  2. Install Racket (instructions depend on your operating system)
  3. Launch DrRacket

By default, DrRacket will either be using the Racket language or no language will be selected. In this course, we will be using R5RS. For ease of use, we will configure DrRacket making R5RS the default language.

If you are using the lab machines, you also need to do these steps!

  1. In the bottom-left corner, click on “Choose language” and click once again on “Choose language”
  2. Expand the window using “Show Details” and click on “Other Languages”
  3. Select under “Legacy Languages” the language “R5RS”
  4. On the right-hand side uncheck the box next to “Disallow redefinition of initial bindings”
  5. Click “OK”

Verify whether “Determine language from source” is changed to “R5RS custom”.

After running the program (it can be empty) the Read-Eval-Print-Loop (REPL) is shown on the bottom of the screen. Use this prompt to evaluate Scheme expressions. If you are building a larger program, it might be better to write your code at the top of the screen (the definitions window). Running the program resets the REPL and executes the definitions from the definitions window and shows its results REPL. Afterwards, you can still interact with your program.

If you are using the terminal (command line):

  1. Be sure that Racket is available on your path.
    • For Windows: Add the bin directory of your Racket installation (usually in C:\Program Files (x86)\Racket v7.1\bin) to your path. Read How to Edit Your System PATH for Easy Command Line Access in Windows for more information (note that this guide is about adding the Android Developer tools to the PATH, so be sure to enter the correct racket path!)
    • For Linux: If you installed Racket via your package manager, it should already be available on the Path. If you used the official installer, follow its instructions. Make sure to install it globally if you want to make it available to every user on your system.
    • For Mac: Execute the following command: sudo sh -c 'echo "/Applications/Racket v7.1/bin" >> /etc/paths.d/racket' (change the path and version number if necessary)
  2. Restart your terminal (exit and reopen)
  3. Type in plt-r5rs and press ENTER. You have installed Racket correctly if the Read-Eval-Print Loop is started.

For all exercises, start Scheme by running plt-r5rs --no-prim <filename> (or without <filename> for a REPL).

Documentation

The official documentation of R5RS can be found on https://schemers.org/Documents/Standards/R5RS/r5rs.pdf. It contains an overview of all syntactical constructs, as well as all built-in procedures. Use this material as a guide for completing these exercises. Pages 48-50 contain an overview of all concepts, keywords and native procedures.

Section 1: Getting used to prefix notation

Scheme uses prefix notation for procedure application, not infix notation as in most programming languages.

Even defining variables uses a prefix notation.




		

In C:




		

In Python:




		

Regular function application in these languages already use prefix notation (e.g. avg(a, b ,c)). However, this is different for mathematical expressions…

In Scheme:




		

In C:




		

In Python:




		

Defining procedures also is different in Scheme…

In Scheme:




		

In C:




		

In Python:




		

Exercise 1: Conversion to prefix notation

Convert the following mathematical expressions in prefix notation using proper indentation.

\[x = \frac{a + b}{e} - \frac{c + d}{f}\]

\[y = c + \frac{a}{b \times c + \frac{d}{e + \frac{f}{g}}}\]

\[z = \frac{a + \frac{b}{c}}{d} \times \frac{e}{\frac{g}{i} - h}\]

To create new variables, write (define <name> <value>).

In order to verify your solutions, put the following definitions at the top of your file and check whether you get the same results as your neighbour.




		

Exercise 2: Predict the result of the following expressions

Predict, on paper, the result of evaluating the following expressions in order. After making a prediction, verify your assumption by evaluating it in the Read-Eval-Print-Loop in DrRacket.




		

Section 2: Building procedures

Remember this example from earlier?




		

This program creates a new procedure called avg that has three formal parameters: a, b and c. Its body contains the single expression (/ (+ a b c) 3). Note that there is no return statement in Scheme, the last expression in the body of a procedure is returned as the result of applying a procedure.

Note! that there is a difference between procedures and functions, but this difference is not important at this point!

Exercise 3: Temperature conversion

Create a procedure that converts temperatures in Celsius to Fahrenheit. Use the following formula as a starting point.

\[F = (C + 40) \times 1.8 - 40\]

Create a procedure that converts temperatures in Fahrenheit to Celsius.

Exercise 4: Areas and perimeters

Create a number of procedures that are able to calculate the perimeter and area of the following shapes. You can choose which parameters each procedure expects.

Section 3: Recursion and Iteration

In programming languages like C writing the following code is often frowned upon.




		

Since every recursive call of fac results in stack space being used, which can result in a stack overflow for large numbers (despite the program being valid C code). A recursive call in tail-position is where the return statements returns immediately the result of doing a recursive tail-call.




		

A good compiler/interpreter will optimise this code such that it will reuse the same stack frame. In other words, the recursive call in the following code does not need to push information on the call stack. This is an optimisation that Scheme enforces for its implementation (which is not the case for C, although some C compilers will optimize this!).

Therefore, the equivalent Scheme program of the previous code listing will be optimized!

Exercise 5: Factorial!

Create a procedure (called fac) that calculates the factorial of a number. Explain what happens when you calculate (fac 5).

Is your solution tail-call recursive? If not, adapt your solution.

Exercise 6: Collatz conjecture

The Collatz conjecture is an unsolved conjecture in mathematics concerning a property of following sequence. Given any positive integer \(n\), the next number in the sequence can be found using the following formula.

\[ f(n) = \begin{cases} n / 2 \ &\text{if } n \ \text{is even}\\ 3 \times n + 1 & \text{if } n \ \text{is odd}\end{cases} \]

The conjecture describes that that no matter what initial value is chosen for \(n\), the sequence will always reach 1. So far, the conjecture has not been proven nor disproven.

For the first part of this exercise, write two procedures.

Tip! Make use of display and newline to display each value in the sequence.

Afterwards, modify your code such that instead of just stopping the recursion when the number 1 is reached, the total amount of iterations is displayed. In other words, given a number \(n\), return the distance to 1.

Are any of your solutions tail-call recursive? If not, change your code such that they are.

Section 4: Anonymous Procedures

Procedures in Scheme are first-class citizens in Scheme: they are regular values that can be passed around via procedure application, and can be stored in variables and data structures.

However, Scheme also contains the concept of anonymous procedures, which do not have a name but that can still be passed around via procedure application.

Exercise 7: Lambda notation

lambda is used for creating anonymous procedures, which are procedures that do not have a name. Just like reguler procedures, they are first-class values. For each of the expressions in the table, create a definition for the f variable such that the output matches.




		
Expression Output
f 1
(f) 2
(f 3) 3
((f)) 4
(((f)) 3) 5

Exercise 8: Higher-order Procedure (Exercise 1.41 from SICP)

Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned when the following program is executed?




		

Exercise 9: Function composition

Write a procedure compose that composes two other procedures (i.e., \(f \circ g\)).




		

Tip! For simplicity, you can asume that both functions given to compose only have one parameter.