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 |
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.
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.
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.
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.
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.