% A TeX version of my CCSC97 Paper		
\documentclass{article}
\usepackage{html}
\begin{document}
\include{body.tex}
\title{IT'S ALL IN THE LANGUAGE\\
(Yet Another Look at the Choice of Programming
Language for Teaching Computer Science)}

\author{John E. Howland\\
Department of Computer Science\\
Trinity University\\
715 Stadium Drive\\
San Antonio, Texas  78212-7200\\
Voice:  (210) 736-7480\\
Fax:  (210) 736-7477\\
Internet:  jhowland@ariel.cs.trinity.edu\\}
\date{March, 1997}
\maketitle

\begin{abstract}
\noindent The choice of which programming language to use in introductory computer science 
courses is guaranteed to spark debate in the computer science community.  Programming 
languages used in computer science instruction have followed various trends or fads within 
the computing industry.  The language choice has often been between languages which are 
currently in wide use by industry for software production.  While it is true that computer 
science education has a responsibility to achieve a balance between providing training in 
current practices within the field and core concepts and theory, it is felt that computer 
science education should not be overly influenced by popular trends when choosing a 
programming language to use in the teaching of introductory computer science.  This paper 
offers other criteria for the choice of language together with examples.\footnote{This
paper appears in the Journal of Computing in Small Colleges, Volume 12, Number 4,
Pages 58-74, March 1997.  Copyright \copyright 1997 by the Consortium for
Computing in Small Colleges.  Permission to copy without fee all or
part of this material is granted provided that the copies are not made
or distributed for direct commercial advantage, the CCSC copyright notice
and the title of the publication and its date appear, and notice
is given that copying is by permission of the Consortium for Computing
in Small Colleges.  To copy otherwise, or to republish, requires a fee
and/or specific permission.  The paper was presented at the CCSC South-Central Conference,
April 11, 1997, San Antonio, Texas.}
\end{abstract}

\section{Introduction}

The choice of which programming language to use in introductory computer science 
courses borders on being a religious issue in which divides computer science departments 
over issues involving what are believed to be practical skills required by industry and the 
requirements of pedagogy.  More often, in the past, industrial requirements have prevailed 
as witnessed by the use of languages such as Cobol, FORTRAN, PL/I and more recently C 
and C++.  Languages have been developed which have, in part, focused on education, i.e. 
Pascal, Modula, etc., but these languages have not become a dominant force in the 
commercial production of software.  At least one computer scientist~\cite{Dijk:cruel} has advocated 
the use of an unimplemented programming language to teach computer science which 
necessarily forces programming instruction to be purely an intellectual activity.  Recent 
growth in Internet activity has provided stimulus for the development of software systems 
which may be executed on a variety of different hardware/software environments.  One of 
these, Java, which uses an abstract Java virtual machine to host the software is remarkably 
similar in overall concept to the Pascal P machine.  Because of Internet popularity, Java is 
now proposed by some as a suitable vehicle for teaching computer science.  Trends or fads 
come and go in computer science education just as in other fields.  This paper attempts to 
re-address an old topic, using a different approach than has been used in the past.

In each of the programming languages mentioned above, it is not clear that the 
choice to use the language for computer science instruction is made primarily for 
pedagogical reasons.  In Section~\ref{sect:criteria}, criteria are given which are based on 
requirements of computer science instruction, particularly use of programming notation in 
an expository fashion in the teaching of introductory computer science.

\section{Criteria}

\label{sect:criteria}
Students who begin majors in computer science more often than not have already 
had one or two courses in computer programming as preparation for college studies.  The 
languages used are often Basic, Pascal, C or C++.  These students, when taking 
introductory college courses which use these same languages, often are insufficiently 
challenged.  A different language choice, based more on instructional needs, which they 
have not previously studied, has the potential of being a leveling experience among the 
students.  Those with prior programming experience in Pascal, C or C++ have no 
particular advantage over those students who have no experience in these languages.

In the following sections, a number of criteria are given which the author feels are 
important in choosing a language for introductory computer science instruction.  
Programming notation ought to be usable as an expository notation to describe all of the 
topics considered in introductory computer science.  Two programming notations, Scheme 
and J, are used as examples of languages which are proposed as being preferable to Basic, 
Pascal, C or C++ under each of these criteria.

\subsection{Interactive Environment}

The advent of computer equipped classrooms where the instructor and students 
have workstations and network based systems for using language aware electronic 
blackboards has increased the importance of an interactive environment for a language.  By 
interactive, we mean systems which operate in a read-evaluate-print loop.  One enters an 
expression which is parsed, analyzed and evaluated in real time and then results are printed 
and the process is repeated.  Of course such systems may be run in batch mode reading 
from standard input and writing to standard output with input/output redirection.  Also, 
although such systems are often implemented as interpreters, the interactive Scheme and J 
systems may also have compilers which are capable of generating binary machine language 
programs.

\subsubsection{Scheme Example}

The Scheme system illustrated here prompts the user for input with ``\verb+> +''.  System 
output starts at the left margin.
\begin{verbatim}
> (map + '(1 2 3) '(10 20 40))
(11 22 43)
>
\end{verbatim}
\subsubsection{J Example}

The J system illustrated here prompts the user for input with three spaces.  System 
output starts at the left margin.
\begin{verbatim}
   1 2 3 + 10 20 40
11 22 43
\end{verbatim}

\subsection{Sentence Structure}

When using programming notation in an expository notation for computer science, 
it is important that the notation have a sentence structure that can be easily verbalized.  
When reading and thinking in an explicit manner, we actually verbalize our thoughts even 
though we are not speaking out loud.  Conventional programming languages are often 
difficult to verbalize and because of this are not as suitable for exposition as are languages 
which are more easily verbalized.  Dijkstra~\cite{Dijk:humble}, in his Turing lecture, ``The Humble 
Programmer'', stated ``... that the tool we are trying to use and the language or notation we 
are using to express or record our thoughts are the major factors determining that we can 
think or express at all!''.  The expressive power of a language is one yardstick by which 
one may measure the relative merits of a programming language.

A programming notation which is used in an expository manner should have a 
simple syntax which is easy to learn and an easily understood evaluation rule.

\subsubsection{Scheme Sentences}

Scheme sentences are sequences of words separated by spaces, preceded and 
followed by ``('' and ``)''.  The first word of a sentence is a verb (or verb like special word) 
which is applied to the remaining words in the sentence.  For example:
\begin{verbatim}
> (* 2 3)
6
\end{verbatim}
is verbalized as times 2 3.  Some sentences use special words which are technically not 
verbs.  An example is:
\begin{verbatim}
(if (< a b)
     a
     b)
\end{verbatim}
This sentence may be verbalized as If less than a b, then a, else b.  The word if 
is not a verb which means that an if sentence has a special evaluation rule.  There are 
relatively few special words and hence relatively few exceptions to the normal rule for 
sentence formation.

Compound sentences may be formed as in:
\begin{verbatim}
(* (- a b) (- a c))
\end{verbatim}
which might be verbalized as Times the quantity minus a b and the quantity minus a c.

\subsubsection{J Sentences}

J sentences are sequences of words separated by spaces.  Most sentences are 
limited to one physical line and are read from left to right.  The J primitive words are 
formed from the ASCII character set.  Primitive words are represented with a single 
character or a character followed by a period or colon.  For example, > represents larger 
than, >. larger of and >: increment.  Terminology from English grammar is used to 
describe J.  Functions are referred to as verbs, constants as nouns, names assigned to 
values as pronouns and names assigned to verbs as proverbs.  Infix conventions are used 
which means that dyads (verbs having two nouns or pronouns as inputs) are written 
between the nouns while monads (verbs having one noun or pronoun as input) are written 
before the noun.  For example:
\begin{verbatim}
   2 * 3
6
\end{verbatim}
is verbalized as 2 times 3.  Compound sentences may be formed as in:
\begin{verbatim}
   2 * 3 + 4
14
\end{verbatim}
which might be verbalized as 2 times, 3 plus 4.  With the exception of subordinate clauses 
enclosed in parentheses, verbs are evaluated in the order from right to left so that the 
sentences may be read from left to right.  The right input to a verb is the value of the entire 
expression to the right and the left input is the value of the noun immediately to the left of 
the verb.  Most verb symbols have two interpretations (dyad or monad) and the choice 
between interpretations is determined by the context as illustrated by the sentence:
\begin{verbatim}
   4 - - 2
6
\end{verbatim}
which is verbalized as 4 subtract negate 2.  Punctuation (parentheses) may be used to 
modify the order of evaluation as in:
\begin{verbatim}
   (2 * 3) + 4
10
\end{verbatim}
which is verbalized as The quantity 2 times 3 plus 4.

In J, verbs may be modified by adverbs or conjunctions to form new verbs which 
are then applied to inputs.  For example, in:
\begin{verbatim}
   +/1 2 3 4
10
   */1 2 3 4
24
\end{verbatim}
the first is verbalized as plus insert the list 1 2 3 4 while the second is verbalized as times 
insert the list 1 2 3 4.  In each of these sentences, the adverb insert (spelled "/") modifies 
the verb (plus or times) producing a new verb which sums or multiplies the elements of the 
list.  Adverbs or conjunctions have precedence over verbs with the left input being the 
entire verb phrase on the left.

\subsubsection{Programs}

	In both Scheme and J, programs and data are represented by the same notation; lists 
in Scheme and lists or arrays in J.  This closely models the situation of storing both 
programs and data in the memory of a computer in numeric form.

\paragraph{Scheme Programs}

	A single sentence is a simple Scheme program.  For example:
\begin{verbatim}
> (* (+ 4 5) (- 3 2))
9
\end{verbatim}
	Functions may be defined as compound sentences involving the special words 
define and lambda.  For example:
\begin{verbatim}
(define square
    (lambda (x)
      (* x x)))
\end{verbatim}
Then
\begin{verbatim}
> (square 10)
100
\end{verbatim}
	Data is described using the special word quote as follows:
\begin{verbatim}
(define people
    (quote ((Clinton (president United States))
            (Dole (wanted to be President))
            (Perot (also wanted to be President)))))
> (length people)
3
\end{verbatim}
\paragraph{J Programs}

	A single J sentence is also a program.  For example:
\begin{verbatim}
   (4 + 5) * (3 - 2)
9
\end{verbatim}
	The J word "=:" assigns (binds) a name (pronoun) to a value (noun).  For 
example, suppose we have defined the following words:
\begin{verbatim}
   monad =: 3
   define =: :
\end{verbatim}
Then the sentence:
\begin{verbatim}
   square =: monad define 'y. * y.'
\end{verbatim}
is an explicit definition for the square function.  The pronoun "y." always refers to the 
input of a monad.  Given this definition, then we may write:
\begin{verbatim}
   square 10
100
\end{verbatim}
 The J notation provides great expressive power when defining functions through an 
alternate method called tacit definition.  A feature of tacit definition is there is no reference 
to the inputs of a definition.  For example, square could also be defined as:
\begin{verbatim}
   square =: ^&2
\end{verbatim}
Here we are using a conjunction (a verb producing verb) called bond (spelled ``\&'') which 
takes a verb input on the left (power function, spelled ``\verb+^+'') and a noun input (2) on the 
right and produces a new verb which squares its argument.  Square could also be defined 
as:
\begin{verbatim}
   square =: *~
\end{verbatim}
Here we use the adverb reflex (spelled ``\verb+~+'') which takes a dyad as its left input and 
converts the dyad into a monad by using its input y. as its left and right input for the dyad.  
In this case the verb derived from *~ y. is y. * y. .

Finally, the square function occurs frequently enough in programs so that it is 
provided as a primitive function in J, (spelled "*:".  So we could also write:
\begin{verbatim}
   square =: *:
\end{verbatim}

\subsection{Model Building}

\label{sect:modeling}
A technique, useful in the teaching of computer science, is to use programming 
notation to build small working models of the topic being described.  A successful 
notation, in this application, will provide concise, but fully accurate, working models.  
Both Scheme and J excel in model building.  Suppose we wish to use recursive definitions, 
in a divide and conquer fashion, to model both recursive and iterative processes.  This 
technique is often used when analyzing the fibonacci sequence.  We use this example to 
illustrate not only modeling techniques but also illustrate the expressive power of Scheme 
and J to describe recursive and iterative processes and continuations.

\subsubsection{Modeling Processes with Scheme}

\label{sect:schememodel}
The fibonacci sequence 0 1 1 2 3 5 8 13, ... may be generated by the recursive 
definition:
\begin{verbatim}
(define fibonacci
  (lambda (n)
    (if (< n 2)
      n
      (+
        (fibonacci (- n 1))
        (fibonacci (- n 2))))))
\end{verbatim}
When analyzing this recursive definition, it is useful to define a related function, 
fib-work, whose value, given an input n, is the number of times fibonacci is called 
when evaluating \verb+(fibonacci n)+.  It is easy to show that fib-work may be defined 
as:
\begin{verbatim}
(define fib-work
  (lambda (n)
    (if (< n 2)
      1
      (+ 1
        (fib-work (- n 1))
        (fib-work (- n 2))))))
\end{verbatim}
fib-work, itself, generates the values of a kind of fibonacci sequence.  If it is our goal to 
evaluate either of these functions for inputs greater than 25 to 30, it is necessary to convert 
these definitions to definitions which result in iterative processes.  A recursive definition 
for fib-work which results in an iterative process is given by the definition:
\begin{verbatim}
(define fib-work-iter
  (lambda (n) (fib-work-iter-helper 1 1 n)))

(define fib-work-iter-helper 
  (lambda (a b count)
    (if (= count 0)
      b
      (fib-work-iter-helper (+ 1 a b) a (- count 1)))))
\end{verbatim}
Suppose f is a compound expression and e is a sub expression of f.  The 
continuation of e in f is that function of a single input x, (lambda (x) ...) which 
contains the execution in f which remains to be done after evaluating the sub expression e.  
This means that the value of the entire expression f may be obtained by evaluating 
((lambda (x) ...) e).  Continuations allow a compound expression to be factored 
into an expression e which is evaluated first and a function which may be called with the 
resulting value of e as an input.

The idea of a continuation may be used to define tail recursive functions.  A 
function is tail recursive if the continuation of each recursive reference in the definition is 
the identity function.

Analysis of fib-work-iter reveals that the work of this definition is done by 
the recursive definition fib-work-iter-helper which has one recursive use of fib-
work-iter-helper whose continuation is the identity function.  Hence, fib-work-
iter is tail recursive which means that its process is iterative.  Here we are assuming that 
any tail recursive definition will be optimized by the Scheme system so that an iterative 
process will be generated.  This will be true of any standard Scheme implementation.  The 
end result of all of this is that fib-work-iter will easily evaluate the fib-work function for the 
input value 100. Indeed,
\begin{verbatim}
> (fib-work-iter 100)
1146295688027634168201
\end{verbatim}
\subsubsection{Modeling Processes with J}

\label{sect:jmodel}
We express the same example used in Section~\ref{sect:schememodel} using the J notation to show 
the expressiveness of J for modeling and recursive and iterative processes.

The fibonacci sequence 0 1 1 2 3 5 8 13, ... may be generated by the recursive 
definition:
\begin{verbatim}
fibonacci =: monad define script
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2
end.
)
\end{verbatim}
When analyzing this recursive definition, it is useful to define a related function, 
fib\_work, whose value, given an input n, is the number of times fibonacci is called 
when evaluating fibonacci n .  It is easy to show that fib\_work may be defined 
as:
\begin{verbatim}
fib_work =: monad define script
if. y. < 2
  do. 1
  else. 1 + (fib_work y. - 1) + fib_work y. - 2
end.
)
\end{verbatim}
As in Section~\ref{sect:schememodel}, fib\_work, itself, generates the values of a kind of fibonacci 
sequence.  If it is our goal to evaluate either of these functions for inputs greater than 25 to 
30, it is necessary to convert these definitions to definitions which result in iterative 
processes.  A recursive definition for fib\_work which results in an iterative process is 
given by the definition:
\begin{verbatim}
fib_work_iter =: monad define 'fib_work_iter_helper 1 1 , y.'

fib_work_iter_helper =: monad define script
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. b
  else. fib_work_iter_helper (1 + a + b) , a , count - 1
end.
)
\end{verbatim}
Again, as in Section~\ref{sect:schememodel}, we may define the idea of a continuation.  Suppose f is 
a compound expression and e is a sub expression of f.  The continuation of e in f is that 
monad having input y.,  monad define '... y. ...' which contains the 
execution in f which remains to be done after evaluating the sub expression e.  This means 
that the value of the entire expression f may be obtained by evaluating:
\begin{verbatim}
monad define '... y. ...' e.
\end{verbatim}
Since the continuation of each recursive use of fib\_work\_iter\_helper in the 
definition of fib\_work\_iter\_helper is the identity function, fib\_work\_iter 
generates a more efficient iterative process so that:
\begin{verbatim}
   fib_work_iter 100x
1146295688027634168201x
\end{verbatim}
The J numeric suffix "x" indicates that an exact numeric representation should be 
used in this computation.

\subsection{Experimentation}

Experimental methods play an important role in computer science and should be a 
part of the introductory computer science curriculum.  Measuring program performance, 
testing experimental hypotheses are areas where traditional scientific methodology may be 
used.  Scheme and J systems provide facilities for measurements of memory space and 
execution time of programs.  As an example of a simple experiment which might be 
performed by introductory students, consider the problem of estimating the execution time 
of the recursive fibonacci function discussed in Section~\ref{sect:modeling}.  In Section~\ref{sect:jfib}, a J 
version of this experiment is described.  The Scheme description of this experiment is 
similar.

\subsubsection{Using J to Estimate the Time to Evaluate fibonacci 100}

\label{sect:jfib}
First define the time verb using the external conjunction.  time returns the time in 
seconds to evaluate the sentence given as its right input.
\begin{verbatim}
time =: 6 !: 2
\end{verbatim}
Next, using the definition of fibonacci given in Section~\ref{sect:jmodel}, determine the 
speed, in calls per sec to fibonacci, of fibonacci n for values of n not more than 
about 25.  Note that you need to use the fib\_work\_iter function from Section~\ref{sect:jmodel} to 
compute these speeds.  For example, on a RISC workstation you might measure this speed 
as:
\begin{verbatim}
   (fib_work_iter 20) % 10 time 'fibonacci 20'
2650.24
\end{verbatim}
This measurement gives a speed of about 2650 calls per sec as determined by the 
average of 10 evaluations of fibonacci 20.

The next step of the experiment involves dividing fib\_work\_iter 100 by 
2650 to obtain the estimate of the time in seconds to evaluate fibonacci 100.  This 
division requires exact integer division which is expressed in J as:
\begin{verbatim}
   0 2650 #: 1146295688027634168201x
432564410576465723x 2251x
\end{verbatim}
Ignoring the remainder of 2251 we have a result of 432564410576465723 seconds 
(the suffix "x" indicates an exact integer).  Students performing this lab are always 
surprised to learn that this time is 13,716,527,478 years, 350 days, 4 hours, 55 minutes 
and 23 seconds.  This result is easily expressed in J as:
\begin{verbatim}
   0 365 24 60 60 #: 432564410576465723x
13716527478x 350x 4x 55x 23x
\end{verbatim}
 
\subsection{Reasoning About Programs}

Myers~\cite{Myer:logic} makes compelling arguments that an introduction to formal methods 
should be a part of introductory computer science courses.  Such methods include the 
topics of proof of program correctness, analytic methods of transformation and 
simplification of programs, etc.  Since both Scheme and J are derived from formal 
mathematical notation it is not surprising that they may be used to introduce and describe 
formal methods in computer science.  In~\cite{Ive:jdict}, Iverson describes J as "... a formal 
imperative language.  Because it is imperative, a sentence in J may also be called an 
instruction, and may be executed to produce a result.  Because it is formal and 
unambiguous it can be executed mechanically by a computer, and is therefore called a 
programming language.  Because it shares the analytic properties of mathematical notation, 
it is also called an analytic language."

\subsubsection{Using J for Proofs}

Iverson and others have written several books which use J to describe a number of 
computing related topics.  One of these~\cite{Ive:concrete} uses J in a rather formal way to express 
algorithms and proofs of topics covered in~\cite{Grah:concrete}.  Following is an example from the 
introduction of~\cite{Ive:concrete}.

A theorem is an assertion that one expression l is equivalent to another r.  We can 
express this relationship in J as:
\begin{verbatim}
t=: l -: r
\end{verbatim}
This is the same as saying that l must match r, that is, t must be the constant 
function 1 for all inputs.  T is sometimes called a tautology.  For example, suppose
\begin{verbatim}
l =: +/ @ i.     NB. Sum of integers
r =: (] * ] - 1:) % 2:
\end{verbatim}
If we define n =: ] , the right identity function, the we can rewrite the last 
equations as:
\begin{verbatim}
r =: (n * n - 1:) % 2:
\end{verbatim}
Next,
\begin{verbatim}
t =: l -: r
\end{verbatim}
Notice that by experimentation, t seems to always be 1 no matter what input 
argument is used.
\begin{verbatim}
   t 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1
\end{verbatim}
	A proof of this theorem is a sequence of equivalent expressions which leads from l 
to r.  
\begin{verbatim}
l
+/ @ i.                            Definition of l
+/ @ |. i.                         Sum is associative and commutative
                                   (|. is reverse)
((+/ @ i.) + (+/ @ |. @ i.)) % 2:  Half sum of equal values
+/ @ (i. + |. @ i.) % 2:           Summation distributes over addition
+/ @ (n # n - 1:) % 2:             Each term is n -1; there are n terms
(n * n - 1:) % 2:                  Definition of multiplication
r                                  Definition of r
\end{verbatim}
Of course, each expression in the above proof is a simple program and the proof is 
a sequence of justifications which allow transformation of one expression to the next.

\subsection{Data Abstraction}

Both Scheme and J allow a functional approach to data abstraction which allows 
data abstractions to be separated from actual representation of abstract data types.  This 
approach provides an interface which defines software layers.  A J example of an abstract 
data type of stack is given.

\subsubsection{J Data Abstraction for Stacks}

\label{sect:stack}
We define the stack data type to be a collection of J items together with the 
following operations:
\begin{verbatim}
make_stack ==> constructs a stack
stackp obj ==> 1 if obj is a stack, else 0
empty_stackp stack ==> 1 if stack empty, else 0
push_stack item ; stack ==> put item on stack
pop_stack stack ==> remove last item pushed on stack
top_stack stack ==> return last item pushed on stack
                      without removing that value from stack
\end{verbatim}
We represent a stack as a J boxed list which has a stack "tag" of 'stack' as its first 
item.  First we define the helping words:
\begin{verbatim}
box =: <
open =: >
match =: -:
first =: {.
append =: ,
drop_last =: _1 & }.
last =: _1 & {

stack_tag =: box 'stack'
the_empty_stack =: box stack_tag
\end{verbatim}
The stack operations may be written as:
\begin{verbatim}
make_stack =: monad define 'the_empty_stack'
stackp =: monad define 'stack_tag match first open y.'
empty_stackp =: monad define 'the_empty_stack match y.'

push_stack =: monad define script
('item' ; 'obj') =. y.
if. not stackp box obj
  do. error 'wrong type second input to push_stack' ; obj
  else. box obj append box item
end.
)

pop_stack =: monad define script
if. not stackp y.
  do. error 'wrong type input to pop_stack' ; y.
  else. box drop_last open y.
end.
)

top_stack =: monad define script
if. not stackp y.
  do. error 'wrong type input to top_stack' ; y.
  else. open last open y.
end.
)
\end{verbatim}
\subsubsection{Using the J stack abstraction}

Following is a sample session using the stack abstraction of Section~ref{sect:stack}.
\begin{verbatim}
   s =: make_stack ''
   stackp s
1                NB. s is a stack
   empty_stackp s
1
   s =: push_stack 1 2 3 ; s  NB. Push the list 1 2 3 on s
   top_stack s
1 2 3
   empty_stackp s
0                NB. s is not empty now
   s =: push_stack 'Some text' ; s  NB. Push a char string on s
   top_stack s
Some text
   s =: pop_stack s
   top_stack s
1 2 3
   s =: pop_stack s
   empty_stackp s
1                NB. s is empty again
\end{verbatim}
\subsection{Procedure Abstraction}

Procedure abstraction is not easily achieved in languages such as Pascal, C or C++, 
however, in Scheme and J, functions are first class entities.  They may be passed as 
arguments, assigned names and returned as values.  Springer and Friedman~\cite{Spring:art} 
describe procedural abstractions in Scheme which solve classes of problems involving flat 
recursion of the top level elements of a list or deep recursion on all sub lists of a list.

\subsubsection{Procedural Abstraction using J}

In J, functions may be passed as arguments and returned as values.  Adverbs are 
functions whose arguments are functions and results are functions.  For example, insert 
(spelled "/") is an adverb which derives a verb result which is inserted between the items of 
its argument.
\begin{verbatim}
   +/ 10 20 50    NB. sum
80
   */ 10 20 50    NB. product 
10000
   -/ 10 20 50    NB. difference
40
\end{verbatim}
Suppose a is defined by:
\begin{verbatim}
   a =: i. 2 3
   a
0 1 2
3 4 5

      +/ a
3 5 7
      */ a
0 4 10
\end{verbatim}
Rank (spelled ", double quote) is a conjunction (a verb producing dyad) produces a 
result verb (derived from its left input) which is applied to its argument according to the 
right input of rank.  For example, a (defined above) has two rows and 3 columns, and is 
said to be of rank 2 (2 dimensions).
\begin{verbatim}
      +/ " 1 a  NB. plus insert applied to the rank 1 items of a (rows)
3 12  NB. row sum
   */ " 1 a  NB. times insert applied to the rank 1 items of a (rows)
0 60  NB. row product
   +/ " 2 a  NB. plus insert applied to the rank 2 items of a (columns)
3 5 7  NB. column sum
   */ " 2 a  NB. times insert applied to the rank 2 items of a (columns)
0 4 10  NB. column product
\end{verbatim}
J supports a number of other abstractions, too numerous to mention in this paper, 
such as hooks, forks, trains, function arrays, gerunds, agenda, power and inverse (where 
defined) for primitive functions as well as explicitly defined functions.

\subsection{Functional and Imperative Programming}

Scheme supports a functional style of programming (when you restrict use of 
procedures which alter already existent object, such as set-car!, set-cdr!, 
vector-set!, vector-fill!, etc.) as well as an imperative style of programming 
when the above mentioned procedures are used.  J is a functional notation where the model 
of computation consists of application of functions to arguments without side effects (roll 
and deal have side effects; pseudo random state is modified).  Once an item is created in 
memory it is never modified; functions may be applied to such items producing new items.  
Functional composition is the primary model for computation.

\subsection{Exact and Inexact Arithmetic}

Scheme and J both support a model of exact integer arithmetic in addition to 
arithmetic of other numeric types such as complex and inexact (floating point) numbers.  
Exact values are limited in precision only by available (possibly virtual) memory.

\subsection{Object Programming}

Object programming combines data structure and operations on data structure to 
entities called objects.  Objects provide abstraction, encapsulation and inheritance to 
provide data based modularization for programs.  Objects are easily modeled in Scheme 
using lexical closures~\cite{How:301notes}, Chapter 6.  Objects may be modeled in J using locales~\cite{How:301notes}, Chapter 6.

\section{Summary}

Languages which are routinely used by industry, such as Basic, FORTRAN, C, 
C++, etc., are often not entirely suitable for expository presentation of topics in the 
introductory computer science curriculum.  Frequently, students entering computer science 
programs have already studied one of these languages and have some programming 
experience.  Choosing a language which is better suited for expository presentation of 
computer science topics, such as Scheme or J, can have a leveling effect amongst students 
who have different preparation for college level training in computer science.  Moreover, 
choosing a language which allows expression of powerful ideas helps give the mindset 
which allows students to think what might otherwise have been "unthinkable" thoughts.  
Such notation should foster development of formal methods in addition to the practical 
aspect of design, analysis and programming.  An important method of exposition involves 
building small working models of each topic.  Once built, such models provide the basis 
for laboratory experimentation which can involve measurements, formulation and 
verification of hypotheses and analysis.

Programming notation becomes a powerful tool of exposition by making an 
appropriate choice of language.  The decision about choice of programming language 
should be made primarily on the basis of how well key concepts in computer science may 
be expressed in the language.  For these reasons Scheme or J is preferable to other 
languages commonly used in introductory computer science courses.

\subsection{Available Implementations}

There are a number of Scheme and J implementations available for nearly every 
machine and operating system including Windows, WindowsNT, MacOS, Linux and other 
varieties of UNIX.  Commercial versions of these languages are available as well, but free 
versions have proven to be more than adequate for laboratory use and students are able to 
install versions of the software identical to lab systems on their own machines.  More 
information on available Scheme software may be found at:
\begin{verbatim}
ftp://ftp.cs.indiana.edu/pub/scheme-repository/
\end{verbatim}
Information on J software may be found at:
\begin{verbatim}
http://www.jsoftware.com .
\end{verbatim}
\subsection{Text Materials}

Several well known introductory computer science text books which use Scheme 
are (most notably)~\cite{Abel:sicp,Frie:proglang,Harv:simply,Mani:schematics,Spring:art}.  Development of the J 
programming language is relatively recent, with the first papers on J appearing in 1991.  To 
this date, the only J based computer science text materials are~\cite{How:cs301}.  However, J has 
been used in an expository fashion to describe several topics in mathematics~\cite{Ive:arith,Ive:calc,Ive:concrete,Reit:fractal}. 

\subsection{Schools Using Scheme or J}

A list of colleges and universities using Scheme in various courses is maintained at 
the Scheme Repository:
\begin{verbatim}
http://www.cs.indiana.edu/scheme-repository/home.html
\end{verbatim}
	Information about the use of the J programming language is maintained at:
\begin{verbatim}
http://www.jsoftware.com/
\end{verbatim}
\begin{thebibliography}{xxxx 99}
\bibitem[Ab 85]{Abel:sicp} Abelson, Harold and Sussman, Gerald with Sussman, Julie. \emph{Structure and 
Interpretation of Computer Programs}, MIT Press, 1985.

\bibitem[Di 72]{Dijk:humble} Dijkstra, Edsger, "The Humble Programmer", 1972 ACM Turing lecture, 
reprinted in ACM Turing Award Lectures, The First Twenty Years, pp 17 - 
31, ACM Press, 1987.

\bibitem[Di 89]{Dijk:cruel} Dijkstra, Edsger, "On The Cruelty of Really Teaching Computing Science", 
1989 SIGCSE Award Lecture, SIGCSE Bulletin, Vol. 21, No. 1, February 
1989.

\bibitem[Fr 92]{Frie:proglang} Friedman, Daniel, Wand, Mitchell and Haynes, Christopher. \emph{Essentials of 
Programming Languages}, MIT Press, 1992.

\bibitem[Gr 89]{Grah:concrete} Graham, Knuth and Patashnik, \emph{Concrete Mathematics}, Addison-Wesley 
Publishing Company, Reading, MA, 1989.

\bibitem[Ha 94]{Harv:simply} Harvey, Brian and Wright, Matthew, \emph{Simply Scheme:  Introducing Computer 
Science}, MIT Press, Cambridge, MA, 1994.

\bibitem[Ho 95]{How:cs301} Howland, John, "A Laboratory Computer Science Course for Liberal Arts 
Students", The Journal of Computing in Small Colleges, Volume 10, Number 
5, May 1995.

\bibitem[How 95]{How:301notes} Howland, John, "Lecture Notes for Great Ideas in Computer Science", Trinity 
University Computer Science Department Lecture Notes,
	   http://www.cs.trinity.edu/About/The\_Courses/cs301/

\bibitem[Ho 96]{How:cs301j} Howland, John, "Using J as an Expository Language in the Teaching of 
Computer Science to Liberal Arts Students", ACM APL96 Conference 
Proceedings, Lancaster University, England, August, 1996.

\bibitem[Iv 91]{Ive:jdict} Iverson, Kenneth, \emph{J Introduction and Dictionary}, Iverson Software, Toronto, 
Canada, 1991.

\bibitem[Iv 92]{Ive:arith} Iverson, Kenneth, \emph{Arithmetic}, Iverson Software, Toronto, Canada, 1992.

\bibitem[Iv 93]{Ive:calc} Iverson, Kenneth, \emph{Calculus}, Iverson Software, Toronto, Canada, 1993

\bibitem[Iv 95]{Ive:concrete} Iverson, Kenneth, \emph{Concrete Math Companion}, Iverson Software, Toronto, 
Canada, 1995.

\bibitem[Ko 94]{Kon:teach} Konstam, Aaron and Howland, John, "Teaching Computer Science Principles 
to Liberal Arts Students Using Scheme", SIGCSE Bulletin 26 (4), December 
1994.

\bibitem[Ma 95]{Mani:schematics} Manis, Vincent S. and Little, James J., \emph{The Schematics of Computation}, 
Prentice Hall, Englewood Cliffs, NJ, 1995.

\bibitem[My 90]{Myer:logic} Myers, J. Paul, "The Central Role of Mathematical Logic in Computer 
Science", SIGCSE Bulletin, Vol. 22, No. 1, February 1990.

\bibitem[Re 95]{Reit:fractal} Reiter, Cliff, \emph{Fractals Visualization and J}, Iverson Software, Toronto, CA, 
1995.

\bibitem[Ri 93]{Rieh:intro} Riehl, Arthur, moderator, "Using Scheme in the Introductory Computer 
Science Curriculum", Panel, SIGCSE Bulletin, Vol. 25, No. 1, March 1993.

\bibitem[Sp 89]{Spring:art} Springer, George and Friedman, Daniel, \emph{Scheme and the Art of Programming}, 
MIT Press, 1989.
\end{thebibliography}
\end{document}
