Transcript Scheme

CSCI 431 Programming Languages
Fall 2003
Scheme
(Section 11.2)
1
Functional Programming
• The design of imperative languages is based directly on the
von Neumann architecture.
• Efficiency is the primary concern, rather than the suitability of
the language for software development.
• The design of functional languages is based on mathematical
functions. A mathematical function is a mapping of members
of one set, called the domain set, to another set, called the
range set.
– e.g., cube(x) = x * x * x
• The objective of the design of a functional programming
language is to mimic mathematical functions to the greatest
extent possible.
• In a functional programming language the evaluation of a
function always produces the same result given the same
parameters. This is called referential transparency.
2
Functional Programming
• The process of computation is fundamentally different in a
functional programming language than in an imperative
language.
• The key idea: do everything by composing functions.
– no mutable state
– no side effects.
• So how do you get anything done in a functional language?
– Recursion (esp. tail recursion) takes the place of iteration.
• In general, you can get the effect of a series of assignments
x := 0
stuff1
x := expr1
stuff2
x := expr2
stuff3
• from f3(f2(f1(0))), where each f expects the value of x as an
argument,f1 returns expr1, and f2 returns expr2.
3
Functional Programming
• Necessary features, many of which are missing in some
imperative languages:
–
–
–
–
–
–
–
1st class functions
serious polymorphism
powerful list facilities
recursion
structured function returns
fully general aggregates
garbage collection
• Lisp (and Scheme) also has
– homoiconography
– self-definition
– read-eval-print
4
Scheme
• Scheme's top level is called the Read-Eval-Print
loop:
– Reads a Scheme expression from the keyboard
– EVALuates it to determine its value
– PRINTs it to the screen
• Examples:
5
Scheme returns 5
5
S-expressions
• To understand Scheme you need to know:
1. What kind of expressions Scheme understands
2. What the evaluation rules are
• Everything in Scheme (data and programs) is
expressed in terms of symbolic expressions, sexpressions
• s-expressions come in 2 basic types
– atoms
– lists
6
Atoms and Lists
• Atoms are constant primitive data objects; there are
different kinds
numbers: 1
1.3
strings: "a string"
symbols: foo
• Lists are the most important data structure. They
consist of 0 or more s-exp's enclosed in parentheses:
(a list) (a list containing (a list)) ()
(((((lots of irritating parentheses!)))))
7
Evaluation rules for atoms
• Most atoms are constants and evaluate to themselves:
5
Scheme returns 5.
"hello"
Scheme returns "hello"
• Symbols are variables and evaluate to their values:
#t
Scheme returns #t
foo
Scheme returns: Error: the variable FOO is unbound
8
Evaluation rules for lists
• Scheme will assume that list structures denote application of
functions to their arguments.
• Function calls are of the following form:
open-paren operator arguments close-paren
(
+
1
2
)
• Extra spaces are ignored, so this expression has exactly the
same effect as a more compact spacing: (+ 1 2)
• Scheme always evaluates the operands and applies the
operation to the result.
• The number of operands or arguments depends on the
operator.
• Each argument can itself be a Scheme expression.
9
Scheme Tutorial
Scheme Tutorial
10
All Values are Pointers
• All values are conceptually pointers to data objects on a heap,
and you don't ever have to explicitly free memory.
• The uniform use of pointers makes lots of things simpler
• Most Scheme implementations optimize away a lot of pointers
– Rather than putting integer values on the heap, most implementations
put the actual integer bit pattern directly into variables.
– A short value (like a normal integer) stored directly into a variable is
called an immediate value
– Each value in each variable actually has a few bits devoted to a type
tag which says what kind of thing it is--e.g., whether it's a pointer or
not.
11
Objects on the Heap
• Most Scheme objects only have fields that are generalpurpose value cells---any field can hold any Scheme value,
whether it's a tagged immediate value or a tagged pointer to
another heap-allocated object.
• A pair (also known in Lisp terminology as a "cons cell") is a
heap-allocated object with two fields. Either field is a generalpurpose value cell.
• The first field of a pair is called the car field, and the second
field is called the cdr field.
• In most implementations, each heap-allocated object has a
hidden "header" field. This extra field holds type information,
saying exactly what kind of heap allocated object it is.
12
Pair Representation
header
Pair-ID
car
15
cdr
10
13
Objects have Type, Variables Don’t
• In Scheme, all variables have the same type: "pointer to
anything."
• Scheme is dynamically typed, meaning that variables don't
have fixed types, but objects do.
• An object carries its type around with it--an integer is an
integer forever, but a variable may refer to an integer at some
times, and a string (or something else) at other times.
• The language provides type-checking at run time to ensure
that you don't perform the wrong operations on objects--if you
attempt to add two strings, for example, the system will detect
the error and notify you.
14
Pairs and Lists
• Suppose we have a variable foo holding a pointer to
a list containing the integers 22, 15, and 6. Here's
two ways of drawing this situation.
foo
pair
pair
pair
30
10
15
*
foo
*
30
10
15
15
Shared Structure
boo
2
foo
*
1
3
5
(define boo (cons ‘2 (cdr foo)))
(define boo (append (list ‘2) (cdr foo)))
16
Equal? vs. Eq?
boo
2
foo
*
5
3
1
We can say that the cdr of foo and the cdr of boo "are eq?,"
because the expression (eq? (cdr foo) (cdr boo)) returns true
boo
*
2
3
5
foo
*
1
3
5
We say that (cdr boo) and (crd foo) “are equal?”
because (equal? (crd boo) (cdr foo)) returns true
17