Make your own free website on Tripod.com

Project 1

Group Members:

VALLURI Vamsidhar, WONG Mei Fun , YEE Meng Yi and ZHANG JingYuan

 

Scheme

History | Overview of Language | Handling of Data Objects | Handling of Sequence Control | Handling of Subprograms and Storage Management | Handling of Abstraction and Encapsulation | Comparison and Contrast with Lisp | Reference |

 

History

Scheme was introduced in 1975 by Gerald J. Sussman and Guy L. Steele Jr. as the first dialect of Lisp to fully support lexical scoping, first-class procedures, and continuations. At first, it was a very small language which was used for research and teaching, support only a handful of predefined syntactic forms and procedures. Now, Scheme is a complete general-purpose programming language. The early implementations of Scheme were interpreter-based and slow. Some modern Scheme implementations boast sophisticated compilers that generate code on par with code generated by the best optimizing compilers for lower-level languages such as C and Fortran.

 

Overview of Language

Scheme is a general-purpose computer programming language. Scheme is also a high-level language, supporting operation on structured data such as strings, lists, vectors, numbers and characters. Scheme is often identified with symbolic applications, its rich set of data types and flexible control structures make it a truly versatile language. Scheme is a fairly simple language to learn. It is based on a handful of syntactic forms and semantic concepts.

Scheme programs are highly portable across implementations of the same Scheme system on different machines. This is because machine dependencies are almost completely hidden from the programmer. Also, because of two related Scheme standardization efforts.

In Scheme, a procedure definition may appear within another block or procedure, and procedure may be invoked at any time thereafter, even if the enclosing block has completed its execution. To support lexical scoping, a procedure carries the lexical context along with its code.

A special case of recursion of Scheme is called tail recursion. It is used to express looping. A tail recursion occurs when a procedure recursively tail calls itself, directly or indirectly. Scheme implementations are required to implement tail calls as jumps (gotos).

Scheme supports the definition of arbitrary control structures with continuations. A continuation is a procedure that embodies the remainder of a program at a given point in the program. When a continuation is invoked, the program immediately continues from that point. It may be obtained at any time during the execution of a program. Continuations allow the implementation of complex control mechanisms including explicit backtracking, multithreading and coroutines.

 

Handling of Data Objects

Scheme handles data values quite differently from most languages. Objects are dynamically allocated in a heap where they are retained until no longer needed, then automatically deallocated. Objects in Scheme are first-class data values because they are heap allocated and retained indefintely, they may be passed freely to procedures, returned as values from procedures and combined to form new objects.

Scheme support many types of objects, including numbers, characters, strings, symbols, and lists or vectors of object. Scheme supports a full set of numeric data types including complex, real and arbitrary-precision rational numbers. This allows Schmes tosupport many numerical applications coded in lower level languages. The following illustrate the data objects in Scheme.

 

Lists and Pairs

The pair or cons cell is the most fundamental of Scheme's structured object types. The most common use for pairs is to build lists. Pairs may be used to construct binary trees. Each pair in the tree structure is an internal node of the binary tree. Proper lists are printed as sequences of objects separated by whitespace and enclosed in parentheses. Brackets ([ ]) may also be used in some Scheme systems.

Numbers

In Scheme, numbers can be integers, rational numbers, real numbers, or complex numbers. This classification is hierarchical, in that all integers are rational, all rational numbers are real, and all real numbers are complex.

Characters

Characters are atomic objects representing letters, digits, special symbols, and certain nongraphic control characters such as space and newline. Characters are written with a #\ prefix, #\A. The characters newline and spcae may be written in this manner as well, but they can also be written as #\newline or #\space.

Strings

Strings are sequences of characters and are typically used as messages or character buffers. Scheme provides operations for creating strings, extracting characters from strings, obtaining substrings, concatenating strings, and altering the contents of strings.

A string is written as a sequence of characters enclosed in double quotes, "hi". A double quote may be introduced into a string by preceding it by a backward slash, "two \"quotes\" within". A backward slash may also be included by preceding it with a backward slash , " \\ slash". Strings are indexed by exact nonnegative integers, and the index of the first element of any string is 0.

Vectors

Vectors are more convenient and efficient than lists for some applications. Whereas accessing an arbitrary element in a list requires a linear traversal of the list up to the selected element, arbitrary vector elements are accessed in constant time. The length of a vector in Scheme is the number of elements it contains. Vectors are indexed by exact nonegative integers, and the index of the first element of any vector is 0.

A vector is written as a sequence of objects separated by whitespace, preceded by the prefix #( and followed by ), #(a b c).

Symbols

Symbols are used for a variety of purposes as symbolic names in Scheme programs. Strings could be used for most of the same purposes, but an important characteristic of symbols makes comparisons between symbols much more efficient. The property that two symbols may be compared quickly for equivalence makes them ideally suited for use as identifiers in the representation of programs, allowing fast comparison of identifiers. This property also makes symbols useful for a variety of other purposes.

Symbols are written without double quotes or other bracketing characters, parentheses, double quotes, spaces, and most other characters with a special meaning to the Scheme reader are not allowed within the printed representation of a symbol.

 

Handling of Sequence Control

Procedure Application

Procedure Application is the most basic Scheme sequence control structure. The syntax is as follow:

( procedure expression …)

Any structure without a syntax keyword in Scheme in the first position is a procedure application. The order of the procedure and argument expressions are evaluated unspecified. It may be left to right, right to left or some arbitrary order ( as specified by the programmer). However, the evaluation is guaranteed to be sequential. Each expression is evaluated before the next evaluation is started.

The example below is to illustrate procedure application.

( + 3 4) => 7

 

Sequencing

To sequence assignments, input/output and other operations, Scheme uses the begin statement.
Syntax: ( begin expression1 expression2, … )
The expression1 expression2 … are evaluated in sequence from left to right.

 

Conditionals

Scheme has conditionals of if statements, not statements, and statements, or statements, cond statements and case statements.

Conditionals for Scheme are of the form:

If statement

Syntax: ( if test consequent alternative)
Syntax: ( if test consequent)
Test, consequent and alternative are expressions. The return value for consequent and alternative will depend on the test value.

Example:
( if (> n 0) 9 = n 10 ) )

 

Not Statement

Syntax: ( not object )
If object is true, the Scheme interpreter will return #t for true, otherwise #f for false.

 

And Statement

Syntax: ( and expression )

The Scheme interpreter evaluates and subexpressions from left to right and stops immediately ( without evaluating the remaining expressions) if any expression evaluates to false. The last value of the last expression evaluated is returned.

Example:
( let ((x 3))
( and (> x 2) ( < x 4))) => #t

 

Or statement

Syntax: ( or expression)
The Scheme interpreter too evaluates or subexpressions from left to right and stops immediately ( without evaluating the remaining expressions) if any expression evaluates to true.

Example:
( let ((x 3))
( or (< x 2) ( > x 4))) => #f

 

Cond statement

Syntax: ( cond expression1 expression2 … )
Syntax: ( cond text expression1 … else …. )
The expressions are evaluated in sequence and return a true a value, the value of the of the last expression is returned.

Example:
( cond

(( = n 10) (= m 1))
(( > n 10) (= m 2) (= n (* n m)))
((< n 10) (=n 0)))

 

Case statement

Syntax: ( case expression1 statement1 statement2 )
The case statement evaluates the expression(s) given and return the value of the corresponding statement.

Example:
(let ((x 4) (y 5))

( case (+ x y)
(( 1 3 5 7 9 ) ‘odd)
((0 2 4 6 8) ‘even)
(else ‘out-of-range))) => odd

 

Recursion and Iteration

Syntax: ( let name ( var val) .. ) expression1 expression2 … )

This form let, called a named let, is a general purpose iteration and recursion construct. This statement returns the value of the final expression.

This statement can also be written as

Syntax: ((letrec (( name lambda (var…) expression1 expression2…))) name) val …)

This statement too returns the value of the final expression. The difference between let and letrec is that letrec allows the definition of mutually recursive procedures.

 

Syntax: ( do ( var val update) … ) ( test res … ) expression)

On each step, the test expression test is evaluated. If the value of test is true, iteration ceases, the result expressions res… are evaluated in sequence and the value of the last expression is returned.

If the value of test is false, the expression are evaluated in sequence, the expressions update… are evaluated, new bindings for var… to the values of update… are created and iteration continues.

 

Syntax: ( for-each procedure list1 list2 … )

The for-each statement guarantees to perform applications in sequence over the lists from left to right.

 

 

Handling of subprograms and storage management

In this discussion, the terms procedure, function, and subprogram will be used interchangeably.

Handling of Subprograms

One of the advantages of using Scheme is that the number of subprograms provided by the language is relatively small, so the programmer does not have to learn to use many subprograms in order to write Scheme programs. Instead, Scheme makes it easy for the programmers to define their own subprograms, as they need them. The lambda syntactic form is used to create subprograms. Any operation that creates a subprogram or establishes local variable bindings is defined in terms of lambda.

Scheme programs are block-structured. Identifiers in Scheme may be bound either at top level or locally. Block structure and lexical scoping help create programs that are modular, easy to read, easy to maintain, and reliable. In Scheme, a subprogram definition may appear within another block or subprogram, and the subprogram may be called at any time after that, even if the enclosing block has completed its execution. To support lexical scoping, a subprogram carries the lexical context or environment along with its code. Furthermore, Scheme subprograms are not always named. Instead, subprograms are first-class data objects like strings or numbers, and variables are bound to subprograms in the same way they are bound to other objects.

Like procedures in many other languages, Scheme procedures may be recursive. There is a special case of recursion in Scheme called tail recursion. It is used to express iteration or looping. A tail call occurs when one subprogram directly returns the result of calling another subprogram. Tail recursion occurs when a subprogram recursively tail calls itself. Scheme implementations are required to implement tail calls as jumps or gotos. As a result, Scheme programmers only need to be familiar with simple procedure calls and recursion and don't need to worry about the usual varieties of loop structures.

Scheme supports the definition of arbitrary control structures with continuations. A continuation is a procedure that embodies the remainder of a program at a given point in the program. When a continuation is called, the program immediately continues from that point. A continuation may be obtained at any time during the execution of a program. As with other subprograms, a continuation is a first-class object and may be called at any time after its creation.

 

Storage Management

Scheme does not have explicit storage management. Objects, are dynamically allocated in a heap where they are kept until no longer needed, then automatically deallocated. A Scheme program never explicitly deallocates scheme objects such as pairs, strings, and procedures. Instead, the storage management system employs garbage collection which automatically reclaims the storage space. The procedure collect in the Scheme language is used for garbage collection. Once the garbage collector proves that the object is no longer referenced, it deallocates the object and the storage used by the object can be reused later. In order to reclaim storage and prevent the system storage from being all used up, garbage collector runs periodically as a program runs. Although garbage collection is performed automatically, Scheme also allows forced garbage collection at a particular time.

Weak pairs and guardians in Scheme also help with storage management. Weak pairs allow programs to maintain weak pointers to objects. A weak pointer to an object does not prevent the object from being reclaimed by the storage management system, but it does remain valid as long as the object is accessible in the system. Guardians allow programs to protect objects from deallocation by the garbage collector and determines when the objects would otherwise have been deallocated. Weak pairs and guardians allow programs to keep information about objects in separate data structures without having to concern about the possibility that maintaining this information will cause the objects to remain indefinitely in the system. Also, guardians allow objects to be saved from deallocation indefinitely so that they can be reused, cleaned-up, or have other actions performed on the data stored within those objects.

 

 

Handling of abstraction and encapsulation

Functional languages are heavily abstracted. A functional program can be viewed as encapsulated inter-operable entities operating at a very high level. . A good portion of the executable code of any functional program is stored in exte

Many functions are currently available as encapsulations of standard functional language libraries. The actual operation of these functions is kept abstracted. The potential complexity of functional programs, as functions are passed a

 

Scheme Built-in Procedures

Scheme environment, starts out with a number of variables bound to locations containing useful values, most of which are primitive procedures that manipulate data. For example, the variable * is bound to (a location initially containing

When a compound expression (E.g. Arithmetic expression like (+ 10 (* 2 5))) is typed (the one surrounded by parentheses) at the Scheme command interpreter, the interpreter treats it as a procedure call, The first expression are the

 

Nested Operations

It is easy to evaluate expressions such as given in the example above. The Primitive Procedure Rule is more powerful, thus, we can use those expressions as parts (or subexpressions) of larger expressions. For instance, consider the

(+ 10 (* 2 5)) =20

This procedure calls for the procedure +, so we need to use The Primitive Rule to evaluate it. The first operand, 10, simply evaluates to itself; and the second operand expression is itself a primitive procedure call, which we can evalu

Procedure Rule. So, there is a hidden recursive equality to our new rule: namely, the notion of "evaluating operand expressions" may itself require the use of other evaluation rules, including the Primitive Procedure Rule.

 

Naming things with Define

In order to give names to objects, we use the expression define. As an example,

(define a 10)
a
(* a 2)

The Scheme interpreter should respond by printing out A, 10, and 20. The first expression tells the Scheme interpreter that henceforth a will be another name for the number 10. In evaluating the second expression, the interpreter evalua

returns the object that a names, 10. In the final expression, we are using the primitive procedure *, so the interpreter has to employ our Primitive Procedure Rule; since the first operand, a, evaluates to 10 and the second opera

value is 20.

 

Evaluating Symbols

In Scheme, we also have a classified define as a special form. The syntax is as follows:

(define symbol expression)

The expression is evaluated as follows: first evaluate the expression following the symbol, and then bind the symbol to the resulting value. Symbols can be bound to data objects (like numbers). To evaluate a symbol, see if it is bound t

that object; if not, signal an error.

Example...

(define a 20)
(define b 2)
(/ a b) = 10

 

Using define to Create New Procedures

(define (double number)
(* 2 number))

The example above is a procedure named double. It is called on one argument, a number, and returns the value of that number multiplied by two.

 

Defining Abstract Objects

This example demonstrates a syntactic extension that facilitates the definition of simple abstract objects. This facility has unlimited potential as the basis for a complete object-oriented subsystem in Scheme.

Abstract objects are similar to basic data structures such as pairs and vectors. Rather than being manipulated via access and assignment operators, however, abstract objects respond to messages. The valid messages and the actions

A particular type of abstract object is defined with define-object, which has the general form

(define-object (name var1 ...)
((var2 val) ...)
((msg action) ...))

The first set of bindings ((var2 val) ...) may be omitted. define-object defines a procedure that is called to create new abstract objects of the given type. This procedure is called name, and the arguments to this procedure become the

The syntactic form send-message is used to send messages to abstract objects. (send-message object msg arg ...) sends object the message msg with arguments arg .... When an object receives a message, the arg ... become the parameters to

The following example should help to clarify how abstract objects are defined and used. The example is a simple kons object that is similar to Scheme's built-in pair object type, except that to access or assign its fields requires sending it messages.

(define-object (kons kar kdr)
((get-car (lambda () kar))
(get-cdr (lambda () kdr))
(set-car! (lambda (x) (set! kar x)))
(set-cdr! (lambda (x) (set! kdr x)))))

(define p (kons 'a 'b))
(send-message p get-car) a
(send-message p get-cdr) b
(send-message p set-cdr! 'c)
(send-message p get-cdr) c

The implementation of define-object is straightforward. The object definition is transformed into a definition of the object creation procedure. This procedure is

the value of a lambda expression whose arguments are those specified in the definition. The body of the lambda consists of a let* expression to bind the local variables and a letrec expression to bind the message names to the action pro

All the above examples throw some light on the type of abstraction and encapsulation the functional language Scheme supports.

 

Comparison and Contrast between Scheme and Lisp

Common Lisp is used for comparison with Scheme.

Handling of Data Objects

In handling of data objects, both Scheme and Lisp adopts lexical scoping and first-class handling. Lexical scoping allows a compiler to determine before program evaluation the scope of all bindings and the the binding which each idetifier reference resolves. However, this does not mean that a compiler can determine the values of all variables since the actual values are not computed until the program executes. Lexical scoping and first class handling help create programs that are modular, easy to read, easy to maintain and reliable.

The data objects supported by Lisp are Numbers, Characters, Symbols, Lists, Arrays, Hash Tables, Readtables,Packages, Pathnames, Streams, Random-states and Structures. Additional categories of data objects are Classes, Methods and Generic functions.

 

Handling of Sequence Control

Basic invocation to function (Lisp) and procedure application(Scheme) has no name. Any list that has no other interpretation as a macro call or special form is taken to be a function call or an procedure application call accodingly. Proceudres in Scheme are first class data objects like strings or numbers and variables are bound to procedures in the same way they are nound to other objects.

Example of Lisp function invocation:

LISP: ( apply # '+' ( )) => 0

Both Scheme and Lisp has implicit simple sequence control structure Scheme uses the construct begin for simple sequencing. LISP uses the implict progn construct.The syntax of the progn construct in Lisp:.

Syntax: progn (form)*

The progn construct takes a number of forms and evaluates them sequentially in order from left to right. The value of the last form is returned by the progn form.

Scheme supports the definition of arbitrary control structures with continuations. A continuation is a procedure that embodies the remainder of a program at a given point in the program. When a continuation is invoked, the program immediately continues from that point. A continuation may be obtained at any time during the execution of a program. As with other procedures, a continuation is a first-class object and may be invoked at any time after its creation. Continuations allow the implementation of complex control mechanisms including explicit backtracking, multithreading, and coroutines.

In addition, Sheme has a special case of recursion called tail recursion. Tail recursion is used to express iteration or looping. A tail call recursion occurs when a procedure recursively tail calls itself, directly or indeirectly. Scheme implementations are required to implement tail calss as jumps(gotoS) so the storage overhead normally associat. When a continuation is invoked, the program immediately continues from that point. A continuation may be obtained at . As with other procedures, a continuation is a first-class object and may be invoked at any time after its creation. , multithreading, and coroutines. ed with recursion is avoided.

However, Lisp does not support continuations or require proper treatment of tail calls, but it does support several less general control structures not found in Scheme. While the two languages are similar, Lisp includes more specialized operators, while Scheme includes more general-purpose building blocks out of which such operators (and others) may be built.

 

Handling of Subprogram

Like Scheme, LISP subprograms might not always be named. Identifiers for subprograms in both languages can be bounded either globally or locally. Both languages allow the creation of large and complex subprograms from small and simple subprograms. Calls to subprograms may be simple call-return or recursive calls although Scheme has a special case of recursion tail recursion. Unlike Scheme, versions of LISP after 1988 do not allow lambda-expression to be used as function arguments.

Common LISP is one of the versions of LISP. Like Scheme but unlike the earlier LISP languages, Common Lisp adopted lexical scoping and first-class procedures. Although Common LISP allows first-class procedures, it discourages the use of procedures as first-class objects by it maintains a separate namespace for procedure variables. Also, Common Lisp does not support continuations or require proper treatment of tail calls, but it does support several less general control structures not found in Scheme. While the two languages are similar, Common Lisp includes more specialized operators, while Scheme includes more general-purpose building blocks out of which such operators and others may be built

 

Storage Management

Both Scheme and LISP allows for dynamic allocation of objects or data values. In both languages, storage is reclaimed periodically. Scheme uses weak pairs and guardians to help with storage management while LISP manage storage by sacrificing one type of storage for another when program gets very large and complex. Unlike Scheme which uses a heap to store objects, LISP uses linked lists that make storage management easier.

 

Handling of abstraction and encapsulation:

Functional languages such as (basic) LISP do not have advanced data types such as classes. The linked list structure as well as the rest of the data structures used in functional languages does not support data abstractions like in obje

Current day implementations of LISP, however, have extensions, which allow LISP programs to be more statement-oriented.

Common LISP is used for comparison with Scheme.

The use of Structures in Common LISP provides some kind of encapsulation.

The essential differences between MIT Scheme's define-structure and Common Lisp's defstruct are:

By default, named structures are tagged with a unique object of some kind. In Common Lisp, the structures are tagged with symbols. This depends on the Common Lisp package system to help generate unique tags; MIT Scheme has no such way to generate uniq

Defining New Type Specifiers in LISP

New type specifiers can come into existence in two ways. First, defining a new structure type with defstruct automatically causes the name of the structure to be a new type specifier symbol. Second, the deftype special form can be used

deftype name lambda-list [[{declaration}* | doc-string]] {form}*

Here are some examples of the use of deftype:

(deftype mod (n) `(integer 0 (,n)))

(deftype list () '(or null cons))

The Common Lisp Object System (CLOS) is an object-oriented extension to Common Lisp. It is based on generic functions, multiple inheritance, declarative method combination, and a meta-object protocol.

The fundamental objects of the Common Lisp Object System are classes, instances, generic functions, and methods.

This extension of Common LISP provides for abstraction and encapsulation, which is, absent in SCHEME.

 

Reference

http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node1.html

http://www.cs.indiana.edu/chezscheme/csug/index.html

http://www.cs.indiana.edu/chezscheme/tspl2d/index.html

 Dybuig, R. Kent. The Scheme Programming Language. New Jersey: Prentice-hall, Inc. 1987.

Wilensky, Robert. Common LISPcraft. New York: W. W. Norton & Company, Inc. 1986.