Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Остальные работы->Реферат
I think that the setting in the short story The Long Rain is a parallel to reality. This short story is set on the planet of Venus, where the rain nev...полностью>>
Остальные работы->Реферат
Also see DPM, Keith J. Holyoak and Paul Thagard, Allison Barnes and Paul Thagard, and Am?lie Frost Benedikt. Analogical Reasoning The simplest variety...полностью>>
Остальные работы->Реферат
I sell here gentlemen, what all the world desires: power. Matthew Boulton, once boasted, speaking of his steam engine factory. James Watt, Boulton s b...полностью>>
Остальные работы->Реферат
The regulation of music in America has been increasing significantly with the advancements of such companies like Napster and the technology to burn o...полностью>>

Главная > Реферат >Остальные работы

Сохрани ссылку в одной из сетей:

Scheme Programming Language Essay, Research Paper

The Scheme programming language

Ken Dickey

An Alternate World View

Each programming language presents a particular world view in the

features it allows, supports, and forbids. This series of

articles describes the world view of the Scheme Programming

Language. This view contains many elements desired in a modern

programming language: multi-paradigm support, composable,

reusable abstractions, ability to create languages specialized

for particular applications, clean separation of the generic and

the implementation specific, and scalability from stand alone

utilities to major software systems.

Scheme started as an experiment in programming language design

by challanging some fundamental design assumptions. It is

currently gaining favor as a first programming language in

universities and is used in industry by such companies as DEC,

TI, Tektronix, HP, and Sun.

WHAT IS SCHEME?

Scheme is a small, exceptionally clean language which is, very

importantly, fun to use. The language was designed to have very

few, regular constructs which compose well to support a variety

of programming styles including functional, object-oriented, and

imperative. The language standard is only about 50 pages,

including a formal, denotational definition of its semantics.

Scheme is based on a formal model (the lambda calculus), so there

are plenty of nice properties for the theoreticians and one can

build knowledgeable code transformation tools reliably.

Scheme has lexical scoping, uniform evaluation rules, and uniform

treatment of data types. Scheme does not have the concept of a

pointer, uninitialized variables, specialized looping constructs,

or explicit storage management.

So what does Scheme look like? Well, it looks a lot like Lisp.

Don’t let this put you off. We can change how it looks (and will

in a future article). But what is important are the concepts

behind it and what you can say with it. So let me make a few

comparisons between Scheme and, say C. You already know that

Scheme is prefix and C is infix:

Scheme C

(+ 2 3 4) (2 + 3 + 4)

(* low x high) ((low * x) && (x * high))

(+ (* 2 3) (* 4 5)) ((2 * 3) + (4 * 5))

(f x y) f(x, y)

(define (sq x) (* x x)) int sq(int x) { return (x * x) }

In Scheme, all data types are equal. What one can do to one data

type, one can do to all data types. This is different from most

languages which have some data types that can do special things

and other data types which are specially restricted. In most

languages numbers have special rights because they can be used

without having names (imagine having to name each number before

using it!). Functions are specially restricted because they

cannot be created without a name.

In Scheme, unnamed functions are created with the key word

lambda.

(lambda (x) (* x x)) -* a function

(define sq (lambda (x) (* x x))

(sq 9) -* 27

((lambda (x) (* x x)) 9) -* 27

((if (foo? x) * +) 2 3 4) -* if (foo? x) is true,

then (* 2 3 4)

else (+ 2 3 4)

(define (curried-add x) (lambda (y) (+ x y))

(define add3 (curried-add 3)) ;; add3 is a funciton

(add3 7) -* 10

((curried-add 3) 7) -* 10

Rubrics:

- Variables can hold values of any type.

- Names refer to values; names are not required.

- An expression is one or more forms between parentheses.

- To evaluate an expression, evaluate all the terms first and

apply the value of the first form to the values of the other

forms. A nested expression counts as a form.

- A comment starts at a semicolon (;) and goes to the end of the

line it is on.

- When a function is evaluated, it remembers the environment

where it was evaluated. {So add3 remembers that X has the value

3 when it evaluates ((lambda (y) (+ x y)) 7).}

(define (sq x) (* x x)) is just syntactic sugar for

(define sq (lambda (x) (* x x))

There are seven kinds of expressions:

Constant: ‘foo #\Z 3 “a string”

Variable reference: foo joe a-long-name-for-an-identifier +

Procedure creation: (lambda (z) (* z z z))

Procedure application: (cube 37)

Conditional: (if (* x 3) sqrt modulo)

Assignment: (set! x 5)

Sequence: (begin (write x) (write y) (newline))

Scheme has the usual assortment of data types:

Characters: #\a #\A #\b #\B #\space #\newline

Strings: “A little string”

Arrays (called vectors): #(1 2 “string” #\x 5)

Lists: (a little (list of) (lists))

Numbers: 47 1/3 2.3 4.3e14 1+3i

Functions (also called procedures)

Booleans: #t #f

Ports (e.g. open files)

Symbols: this-is-a-symbol foo a32 c$23*4&7+3-is-a-symbol-too!

Rubrics:

- A vector’s contents can be any data objects.

- Symbols may include the characters + – . * / * = * ! ? : $ % _

& ~ and ^.

- Symbols are case insensitive.

- Symbols are used for identifiers, so identifiers (variable

names) are case insensitive.

- By convention predicates end in a question mark {e.g. string?}

and side effecting procedures end in an exclimation mark {e.g.

set!}.

Numbers are especially interesting in that an integer is a

rational is a real is a complex. There is no classification of

numbers based on their storage class {e.g. fixed, float, bignum,

…} but on whether or not they are exact.

(exact? 3) -* #t

(exact? 1/3) -* #t

(exact? 2.3##) -* #f

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

(integer? 2) -* #t

(integer? 3/7) -* #f

(real? 2) -* #t

The ZEN of SCHEME

One of the joys of Scheme which initially confuses some people is

the lack of inhibition. Scheme is very expressive, which means

that one can say “the same thing” in many ways. In Scheme one

has the freedom–and the responsibility–of saying exactly what

is desired. We are all used to working around certain language

features to get something done. Scheme gets in the way very

little.

As a warming up exercise, let’s build a pair. A pair consists of

2 elements obtained by the access routines FIRST and SECOND. The

constructor is called PAIR. The relations to be maintained are

(first (pair 1 2)) -* 1 ; (second (pair 1 2)) -* 2. For those of you

who know LISP, this is not much to get worked up over. But how

many ways can we implement the trio: pair, first, second? There

is a virtually endless variety.

;; vector

(define (PAIR a b) (vector a b)) ;; or just: (define PAIR vector)

(define (FIRST aPair) (vector-ref aPair 0))

(define (SECOND aPair) (vector-ref aPair 1))

——

;; selector function

(define (PAIR a b) (lambda (bool) (if bool a b)))

(define (FIRST aPair) (aPair #t))

(define (SECOND aPair) (aPair #f))

——

;; message passing

(define (PAIR (a b)

(lambda (msg)

(case msg ;; we’ll implement CASE in the next article

((first) a) ;; when the message is the symbol first, return a

((second) b)

) ) )

(define (FIRST aPair) (aPair ‘first))

(define (SECOND aPair) (aPair ’second))

——

;; alias

(define PAIR cons)

(define FIRST car)

(define SECOND cdr)

——

;; pure functions

(define (PAIR a b) (lambda (proc) (proc a b)))

(define (FIRST aPair) (aPair (lambda (x y) x)))

(define (SECOND aPair) (aPair (lambda (x y) y)))

The moral of the above is not to assume anything about the

implementation of interfaces–even simple ones.

Now that we are warmed up, let’s take a look at ye ol’ factorial

function on integers.

First, the recursive definition:

(define (fact n)

(if (* n 2)

1

(* n (fact (sub1 n)) ;; (define (sub1 n) (- n 1))

)

When I first learned about recursive definitions like the one

above, the hard thing to get used to was the how the hidden state

kept on the stack. A transformation of the above code makes the

stack visible.

;; the identity function just returns its argument

(define (identity value) value)

;; keep invocation of fact the same, but do something different

(define (fact n) (cfact n identity))

;; the transformed recursive factorial

(define (cfact n k)

(if (* n 2)

(k 1)

(cfact (sub1 n)

(lambda (result) (k (* n result))))

) )

Cfact is the continuation-passing version of fact. The basic

idea here is that instead of returning a result each function

takes an extra argument, the continuation, which is invoked with

the result of the function.

Let’s look at what happens for (fact 3).

(fact 3) is (cfact 3 identity)

(cfact 3 identity) is

(cfact 2

(lambda (result) (identity (* 3 result)))) ;; k’

which is

(cfact 1

(lambda (result^) ;; k”

((lambda (result) (identity (* 3 result))) ; fun k’

(* 2 result^)) ; argument to k’

-*

((lambda (result^) ;; k”

((lambda (result) (identity (* 3 result)))(* 2 result^)))

1)

-*

((lambda (result) (identity (* 3 result))) (* 2 1))

-*

(identity (* 3 (* 2 1)))

-*

(* 3 (* 2 1))

or {as we knew all along}

6

The point of this is not that we can take something simple and

make it look bizarre. So why did I do it? The point is that we

can take control which is typically hidden on the stack at run

time and study and manipulate it as source code. This lets us do

some interesting things. For example, we can ignore the

continuation passed in and use another one. If we are writing a

game or an AI search routine or a mathematical routine which

converges on a result, we can monitor our progress. If our

progress is slow, we can save our continuation–”where we are

now”–and try a different approach. If the newer approach is

even worse, we can go back to our saved continuation and try

again from there. We can of course save our attempt at doing

better to try again just in case it really was better…

So continuation passing can let us build some pretty interesting

control structures. Let’s take another look at the simple

function, fact. When we look at (fact 4), (fact 5), and so on,

we see a common pattern. Each call just stacks up a

multiplication. Since we can see this, we can eliminate the

stack and do the multiplication directly by introducing an

accumulator. We take care of initializing the accumulator by

noting that anything times one is the same as itself {i.e. the

multiplicitive identity: x * 1 = x}.

(define (cfact n k)

;; lexical scope means we can nest functions

(define (ifact x acc k^)

(if (* x 2)

(k^ acc)

(ifact (sub1 x) (* x acc) k^)

) )

(ifact n 1 k)

)

Now this looks a bit strange too. But there is an interesting

detail here. We did not have to build any new continuations!

The continuation k^ which is given the final result is exactly

the original continuation k. This means that the call of ifact,

which looks recursive, is really iterative. When it “calls

itself” it does not add to the stack. The “recursive” call to



Загрузить файл

Похожие страницы:

  1. The Ebonics Debate Essay Research Paper The

    Реферат >> Остальные работы
    The Ebonics Debate Essay, Research Paper The Ebonics Debate On December 18th, 1996, the ... the language the children have to help them acquire the language ... the two debates. I will then examine the two articles using Toulmin=s scheme ... child care programs which are ...
  2. The Millennium Bug Essay Research Paper The

    Реферат >> Остальные работы
    ... Bug Essay, Research Paper The new Millennium – Apocalypse soon? If you haven’t heard of the ... , for example, saw the First World War as a sign that Christ would ... ago rather than learn new programming languages, could suddenly find their skills ...
  3. The United Nations Essay Research Paper The

    Реферат >> Остальные работы
    The United Nations Essay, Research Paper The United Nations There have been ... 26) Even though the regular session of the General Assembly lasts around ... organizations official languages; and conduct information programs to acquaint the world?s communications ...
  4. The Brain 2 Essay Research Paper The

    Реферат >> Остальные работы
    The Brain 2 Essay, Research Paper The Human Brain The ... the brain to the organs, but also send messages from the eyes, ears, skin ... movement. The cerebellum carries small “programs” ... The cortex is a sheet of greyish matter which produces our thoughts, language ...
  5. The Internet Essay Research Paper The Internet (1)

    Реферат >> Остальные работы
    The Internet Essay, Research Paper The Internet: How it Works and How it Effects the World Many ... another on the net. Many people wrote programs that fulfilled the protocol and ... computers mainly operate using the English language, the Internet usually does as ...

Хочу больше похожих работ...

Generated in 0.0031821727752686