CSc 520 - Principles of Programming Languages
34 : Scheme -- Introduction

Christian Collberg

Department of Computer Science

University of Arizona

1 Background

• Scheme is based on LISP which was developed by John McCarthy in the mid 50s.
• LISP stands for LISt Processing, not Lots of Irritating Silly Parentheses.
• Functions and data share the same representation: S-Expressions.
• A basic LISP implementation needs six functions cons, car, cdr, equal, atom, cond.
• Scheme was developed by Sussman and Steele in 1975.

2 S-Expressions

• An S-Expression is a balanced list of parentheses.

More formally, an S-expression is

1. a literal (i.e., number, boolean, symbol, character, string, or empty list).
2. a list of s-expressions.

• Literals are sometimes called atoms.

3 S-Expressions -- Examples

Legal

Illegal

	66
	()
	(4 5)
	((5))
	(()())
	((4 5) (6 (7)))

	(
	(5))
	()()
	(4 (5)
	)(

4 S-Expressions as Trees

• An S-expression can be seen as a linear representation of tree-structure:

SExprTree

5 S-Expressions as Function Calls

• A special case of an S-expression is when the first element of a list is a function name.
• Such an expression can be evaluated.

6 S-Expressions as Functions

• As we will see, function definitions are also S-expressions:

• So, Scheme really only has one syntactic structure, the S-expression, and that is used as a data-structure (to represent lists, trees, etc), as function definitions, and as function calls.

7 Function Application

• In general, a function application is written like this:
  
  
  

• The evaluation proceeds as follows:
  1. Evaluate operator. The result should be a function .
  2. Evaluate
     
     
     
     to get
     
     
     

  3. Apply to .

8 Function Application -- Examples

9 Atoms -- Numbers

Scheme has

• Fractions (5/9)
• Integers (5435)
• Complex numbers (5+2i)
• Inexact reals (#i3.14159265)

10 Atoms -- Numbers...

11 Atoms -- Numbers...

• Scheme tries to do arithmetic exactly, as much as possible.
• Any computations that depend on an inexact value becomes inexact.
• Scheme has many builtin mathematical functions:

12 Atoms -- Strings

• A string is enclosed in double quotes.

13 Atoms -- Booleans

• true is written #t.
• false is written #f.

14 Identifiers

• Unlike languages like C and Java, Scheme allows identifiers to contain special characters, such as ! $ % & * + - . / : < = > ? @ ^ _ ~ . Identifiers should not begin with a character that can begin a number.
• This is a consequence of Scheme's simple syntax.
• You couldn't do this in Java because then there would be many ways to interpret the expression X-5+Y.

Legal

Illegal

	h-e-l-l-o
	give-me!
	WTF?

	3some
	-stance

15 Defining Variables

• define binds an expression to a global name:
  
  

16 Defining Functions

• define binds an expression to a global name:
  
  
• arg arg ... are formal function parameters.

17 Defining Helper Functions

• A Scheme program consists of a large number of functions.
• A function typically is defined by calling other functions, so called helper or auxiliary functions.

18 Preventing Evaluation

• Sometimes you don't want an expression to be evaluated.
• For example, you may want to think of (+ 4 5) as a list of three elements +, 4, and 5, rather than as the computed value 9.
• (quote (+ 4 5)) prevents (+ 4 5) from being evaluated. You can also write '(+ 4 5).

19 Dr Scheme

• Download DrScheme from here: http://www.drscheme.org.
• It has already been installed for you in lectura and the Windows machines in the lab.
• Start DrScheme under unix (on lectura) by saying
  
  
• On Windows and MacOS it may be enough to click on the DrScheme logo to start it up.

20 Dr Scheme

DrScheme1

21 Dr Scheme -- Using TeachPacks

0.4

22 Dr Scheme -- Using the Stepper

0.4

23 References

• Read Scott, pp. 523-527, 528-539.
• Free interpreter: http://www.drscheme.org.
• Manual: http://www.swiss.ai.mit.edu/projects/scheme/documentation/scheme.html
• Tutorials:
  • http://ai.uwaterloo.ca/~dale/cs486/s99/scheme-tutorial.html
  • http://cs.wwc.edu/%7Ecs_dept/KU/PR/Scheme.html
  • http://www.cis.upenn.edu/%7Eungar/CIS520/scheme-tutorial.html
• http://dmoz.org/Computers/Programming/Languages/Lisp/Scheme

24 References...

• Language reference manual: http://www.swiss.ai.mit.edu/ftpdir/scheme-reports/r5rs.ps.
• Some of this material is taken from http://www.ecf.utoronto.ca/~gower/CSC326F/slides, ©Diana Inkpen 2002, Suzanne Stevenson 2001.

25 Scheme so Far

• A function is defined by
  
  
• A variable is defined by
  
  
• Strings are inclosed in double quotes, like "this". Common operations on strings are
  • (string-length string)
  • (string-append list-of-strings)
• Numbers can be exact integers, inexact reals, fractions, and complex. Integers can get arbitrarily large.
• Booleans are written #t and #f.

26 Scheme so Far...

• An inexact number is written: #i3.14159265.
• Common operations on numbers are
  • (+ arg1 arg2), (- arg1 arg2)
  • (add1 arg), (sub1 arg)
  • (min arg1 arg2), (max arg1 arg2)
• A function application is written:
  
  
• Quoting is used to prevent evaluation
  
  or