for
CSCI 1301: Great Ideas in Computer Science
(c) 1993 - 2007 John E. Howland, All Rights Reserved
Department of Computer Science
Trinity University
One Trinity Place
San Antonio, Texas 78212-7200
Internet: jhowland@ariel.cs.trinity.edu
When we ask this question, consider that we don't have car science or telephone science, dishwasher science, etc. Since computing is now an integral part of almost every aspect of modern society, perhaps we should ask whether or not computer science is subsumed by such classical disciplines as mathematics, physics, neuro-science, electrical engineering, linguistics, logic and philosophy. In fact, some computer scientists consider this to be the case and consider it their goal to so thoroughly integrate the various parts of computer science back into its parent disciplines so that it no longer has a separate identity as computer science. This somewhat controversial view is not widely held.
In the previous paragraph a number of terms were used with which you may not be familiar. Do not worry about this now as definitions for most of these will be given later.
Using this definition one might consider some of the sub areas of computer science to involve the design, structure, analysis, efficiency and correctness of algorithms, the mathematical properties of algorthms, the data they manipulate, the languages in which they are implemented and the machines on which they are interpreted.
Finally, one might study the limitations of algorithms.
2 + 3is an example of a simple J sentence. It is verbalized as "2 plus 3". Compound sentences are formed by using parentheses to form subordinate clauses (sub sentences). We don't pronouonce the parentheses unless we have a compound sentence which contains another sentence imbedded within as a subordinate clause. Most J sentences are imperative, that is, they convey some action to be performed by the reader. In the above example, the reader is directed to add 2 and 3 producing a result of 5.
A J computer system is in a repetitive process of reading the user's sentence, evaluating that sentence (performing the imperative action of the sentence) and printing the result of the sentence. We say that the J system has a REPL (Read, Evaluate and Print Loop).
The general form of a J sentence (version 1) is:
<noun>or
<verb> <sentence>or
<sentence2> <verb> <sentence1>Verbs have one or two objects. Examples are:
2 - 3 - 5The first sentence is read "2 subtract 5", producing a result of negative 1. The second sentence is read as "negate 5", producing a result of negative 5. Verbs which are applied to just one item (negate for example) are called monads. Verbs which are applied to two items (addition for example) are called dyads. The terminology <verb> or <sentence> is a notation (actually a meta notation) to describe that a part of speech called a verb or sentence appears in a particular position in the syntax (rules of grammar) of a sentence. Notice that in defining a sentence we are saying that a sentence is defined in terms of itself. We say that such a definition is recursive, i.e. the definition refers in part to itself. This is not a circular definition since a sentence is also defined as a noun. Sentences may have sub-sentences. In this case we say we have a compound sentence. For example:
(2 * 5) - 3 % - 2The first sentence is read "the quantity 2 times 5, subtract 3", producing a result of 7. The second sentence is read "reciprocal of negate 2", producing a result of negative 0.5 . We call such sentences compound sentences. Notice also that there is an implied order in this imperitave sentence. The subordinate sentence (2 * 5) must be read or performed before the subtraction can be performed. There is a "natural" order of evaluation which is derived from a left to right reading of a sentence. For example,
2 * 3 + 4evaluates to the value 14. This surprizing result is derived from the left to right reading as "2 times the quantity 3 + 4". You are perhaps expecting a value of 10 for this expression having learned that multiplications are always performed before addition. This rule was arbitrarily choosen and has no mathematical basis. To achieve the other order of evaluation in J, one must write:
(2 * 3) + 4which evaluates to 10. This sentence is read as "the quantity 2 times 3, plus 4.
In 1.3.2, <verb> and <noun> are meta notation variables which stand for the kind of object which would appear at that place in a sentence.
<verb> <sentence>first evaluate <sentence> ,using the same evaluation rule, then apply <verb> to the resulting value. Notice that this rule is defined in terms of itself. Such rules are said to be recursive. If the sentence is of the form:
<sentence2> <verb> <sentence1>first evaluate <sentence1> , then evaluate <sentence2> and apply <verb> to these resulting values.
The values of a sentences consisting only of verbs and nouns are nouns. A noun in J is a constant value whose meaning is universally understood and never changes. Examples of nouns are 2 (the number), '21' (a list of two characters, namely 2 followed by 1. There are other types of nouns as we shall see later.
A pronoun in J is a symbol or name which has been bound to a noun. A pronoun may be used in place of a noun in sentences. For example,
t1 =: 5.52defines a pronoun t1. Once so defined, t1 may be used as a noun as in the sentence
3 + t1The value of a pronoun may change from time to time, depending on the binding, just as the pronoun she, in the English language, takes on different meanings depending on the context of reference.
A symbol may be bound to a verb creating what is called a proverb. For example we define
plus =: +Then we write 3 plus 4. A proverb may be used in place of a verb in sentences. This is probably an unfamiliar concept in natural language since English does not have a mechanism to define new verbs. The J notation allows us to define pronouns and proverbs with equal ease. We could even write
minus =: +but this would likely lead to confusion. We need to exercise common sense in the choice of symbols used to define pronouns and proverbs to improve the readability of our J sentences.
Pronouns and proverbs are the key to abstraction in J. They allow the binding of a complex value or verb to a name which can then be used to form more complex objects.
noun =: 0 adverb =: 1 conj =: 2 monad =: 3 verb =: 3 dyad =: 4 locale =: 6 define =: : 0The sentence
plus =: dyad define x. + y. )constructs a verb (dyad). The words x. and y. are pronouns which are bound to the left and right nouns when the verb plus is used in a sentence. The last line of this definition, containing only ")", signifies the end of the definition script. The action of this verb is to produce a noun result of adding x. and y. .
10 plus 15This sentence would produce a noun of 25. Actually, we could have defined this verb without using a script or binding a name to the definition. For example:
10 (dyad def 'x. + y.') 15produces the result 25.
The sentence:
square =: monad define y. * y. )defines a monad which squares. Then the sentence
square 5produces the noun 25. This function could be defined without using a script or binding the name square as:
(monad def 'y. * y.') 5which produces a result of 25.
square may be written using the J primitive *: . The expression
*: 5produces a result of 25. We introduce a notation ==> which is read "produces a result of". The ==> is not J notation. It is used in these notes to indicate what value is obtained as a result of evaluation of the J sentence immediately to the left.
maximum =: dyad define if. x. > y. do. x. else. y. end. ) 3 maximum 4 ==> 4 5 maximum 4 ==> 5.We can use an alternate way of expressing this function as a monad. In this definition, both values are combined as a two item list.
maximum =: monad define
('x' ; 'y') =. y.
if. x > y
do. x
else. y
end.
)
This
definition expects its two inputs to be combined using the link verb
(";"), explained in section 1.3.9 below.
maximum 3 ; _4 ==> 3 maximum 3 ; 4 ==> 4In this definition of maximum, the line ('x' ; 'y') =. y. separates the two input items in y. and binds the local name x to the first and y to the second.
l1 =: 1 2 10 _9 3creates a list of 5 numbers, 1, 2, 10, negative 9 and 3. The number of elements in a list is given by the tally (spelled #) verb.
#l1 ==> 5 l2 =: 'Hi there' #l2 ==> 8creates a list 8 characters.
first =: {.
rest =: }.
Then
first l1 ==> 1 rest l1 ==> 2 10 _9 3 first l2 ==> H rest l2 ==> i thereNext, consider the definition
from =: {
Then,
0 from l2 ==> H 3 0 2 from l1 ==> _9 1 10
1 , 2 ==> 1 2 'H','i' ==> Hi 'Hi',' ','there' ==> Hi there 'Hi','there' ==> HithereAnother verb (i.) called integer builds lists of integers, starting with 0.
i. 2 ==> 0 1 i. 10 ==> 0 1 2 3 4 5 6 7 8 9 # i. 10 ==> 10There are two verbs
box =: < open =: >which are useful when building lists.
box i. 5 ==> +---------+ |0 1 2 3 4| +---------+Hence,
(box i. 5) , box i.2 ==> +---------+---+ |0 1 2 3 4|0 1| +---------+---+which is a two element list. Consider
l3 =: (box i. 5) , box i.2Then,
1 from l3 ==> +---+ |0 1| +---+ open 1 from l3 ==> 0 1 tally open 1 from l3 ==> 2 1 from open 1 from l3 ==> 1It is considered a domain error (out of the domain of definition) to apply the append verb to different types of data. For example,
1 2 3 , 'hi there' ==> domain errorThe verb link (;) is designed to solve this problem by boxing its left input and right input, if necessary, producing a list of boxed items.
1 2 3 ; 'hi there' ==> +-----+--------+ |1 2 3|hi there| +-----+--------+ 1 2 3 ; box 'hi there' ==> +-----+--------+ |1 2 3|hi there| +-----+--------+In this latter example, the right input box 'hi there', was not boxed a second time since it is already boxed.
(first x) link rest x ==> xand given two J items a and b:
first a link b ==> a
rest a link b ==> b
We begin the solution by observing that if the list, ls, is non-empty, then the solution can be expressed as (first ls) + list_sum rest ls. We call this type of solution the divide and conquer approach. That is, we have reduced the solution of the original problem to solution of two problems (an addition and summing a smaller list of numbers) each of which is smaller than the original problem. Moreover, one of the sub-problems is identical (except for summing a smaller list) to the original problem. This means we can use the same solution to that sub-problem as we did on the original problem. The only thing that is left is to decide what to return as an answer when list_sum eventually attempts to compute the sum of an empty list. How about zero?
Consider the following definition for list_sum.
list_sum =: monad define if. 0 = tally y. do. 0 else. (first y.) + list_sum rest y. end. ) list-sum 1 2 3 4 ==> 10We can define a traced version of list_sum which will show some of the inner working of the list_sum function as follows:
display =: 1 !: 2 & 2display is a helping monad which displays its input on the display console and then returns that input. Three other functions are used to trace functions. They are given below, but we will not discuss them until later.
trace =: monad define display y. : display (format x.),format y. y. ) entering =: 'Entering, input = '&trace leaving =: 'Leaving, result = '&trace
traced_list_sum =: monad define entering y. if. 0 = tally y. do. leaving 0 else. leaving (first y.) + traced_list_sum rest y. end. ) traced_list_sum 1 2 3 4 Entering, input = 1 2 3 4 Entering, input = 2 3 4 Entering, input = 3 4 Entering, input = 4 Entering, input = Leaving, result = 0 Leaving, result = 4 Leaving, result = 7 Leaving, result = 9 Leaving, result = 10 10The J notation provides an abstraction for the above program as:
+/ 1 2 3 4 ==> 10The phrase +/ is a verb which sums the items of a list.
factorial 0 = 1
factorial n = n * factorial (n - 1) , for n >0.
This leads us to the J definition:
factorial =: monad define if. 0 = y. do. 1 else. y. * factorial y. - 1 end. ) factorial 0 ==> 1 factorial 4 ==> 24 factorial 6 ==> 720As before, we can define a traced version of factorial which will show some of the inner working of the factorial function as follows:
traced_factorial =: monad define entering y. if. 0 = y. do. leaving 1 else. leaving y. * traced_factorial y. - 1 end. ) traced_factorial 6 Entering, input = 6 Entering, input = 5 Entering, input = 4 Entering, input = 3 Entering, input = 2 Entering, input = 1 Entering, input = 0 Leaving, result = 1 Leaving, result = 1 Leaving, result = 2 Leaving, result = 6 Leaving, result = 24 Leaving, result = 120 Leaving, result = 720 720The J notation provides a primitive definition for factorial (!).
!6 ==> 720The abstraction for the list_sum program could be varied slightly to achieve another solution of the factorial verb as:
*/1 2 3 4 5 6 ==> 720The phrase */ is a verb which computes the product of the items of a list.
Notice the similarity between the list_sum and factorial verbs.
1 = 5 ==> 0 1 = 1 ==> 1 'a' = 'A' ==> 0 'a' = 0 ==> 0 'Hi there' = 1 2 ==> length error 'Hi there' = 'e' ==> 0 0 0 0 0 1 0 1The match verb (-:) is available to compare structured items.
'Hi there' -: 1 2 ==> 0
select_positive =: monad define
if. 0 = tally y.
do. ''
else. if. 0 <: first y.
do. (first y.) append select_positive rest y.
else. select_positive rest y.
end.
end.
)
select_positive 1 2 3
1 2 3
select_positive 1 _9 2 _3 3
1 2 3
As
before we can make a traced version of select_positive which will help us
follow the execution of this verb.
traced_select_positive =: monad define
entering y.
if. 0 = tally y.
do. leaving ''
else. if. 0 <: first y.
do. leaving (first y.) append traced_select_positive rest y.
else. leaving traced_select_positive rest y.
end.
end.
)
traced_select_positive 1 2 3 Entering, input = 1 2 3 Entering, input = 2 3 Entering, input = 3 Entering, input = Leaving, result = Leaving, result = 3 Leaving, result = 2 3 Leaving, result = 1 2 3 1 2 3
traced_select_positive 1 _9 2 _3 3 Entering, input = 1 _9 2 _3 3 Entering, input = _9 2 _3 3 Entering, input = 2 _3 3 Entering, input = _3 3 Entering, input = 3 Entering, input = Leaving, result = Leaving, result = 3 Leaving, result = 3 Leaving, result = 2 3 Leaving, result = 2 3 Leaving, result = 1 2 3 1 2 3