Laboratory Experiment 0


Getting Started With the J Programming Notation

The purpose of this laboratory is to introduce the J programming language. There will not be a laboratory problem or lab report due for this lab, but rather, there will be a lecture and demonstration of J and some practice using J.

An Introduction to the J Notation

Since we observed in 1.2.1 that verbalization of notation is important, we use ideas and terminology from natural language (English) to describe the important features of J. This includes both syntax (the rules of grammar) and semantics (what J sentences mean).

J Sentences

In J, a sentence is a collection of items (words). Word formation rules (which we will later learn) are used to break a sentence into words. For example:

 2 + 3

is 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 is:

Sentence Form

<noun>

<verb> <sentence>

<sentence2> <verb> <sentence1>

Verbs have one or two objects. Examples are:

2 - 3
- 5

The 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. 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
% - 2

2 * 3 + 4

evaluates 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) + 4

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

Evaluation Rule

If the sentence consists of just an noun, return the value of that noun. If the sentence is of the form:

<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 sentence 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 which has been bound to a noun. A pronoun may be used in place of a noun in sentences. For example,

t1 =: 5.52

defines a pronoun t1. Once so defined, t1 may be used as a noun as in the sentence

3 + t1

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

Making New Verbs

The real power of a notation which is useful for describing computational ideas is that the users of the notation may make their own verbs. This is something which most of us do not have an opportunity of doing in natural language.

Defining Verbs Explicitly

Suppose that the following definitions have been made.

noun =: 0
adverb =: 1
conj =: 2
monad =: 3
dyad =: 4
define =: : 0

The 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 15

This sentence would produce a noun of 25. Actually, we could have defined this verb without binding a name to the definition. For example:

10 (dyad def 'x. + y.') 15

produces the result 25.

The sentence:

square =: monad define
y. * y.
)

defines a monad which squares. Then the sentence

square 5

produces the noun 25. This function could be defined without binding the name square as:

(monad def 'y. * y.') 5

which produces a result of 25.

square may be written using the J primitive *: .

Conditional Definitions

Any notation for describing computation needs a method for creating action sentences which do one action if a certain condition is true and another action if that condition is not true. There is a special keyword if. to accomplish this. Here is an example:

maximum =: dyad define
if. x. > y.
  do. x.
  else. y.
end.
)

3 maximum 4 evaluates to 4, while 5 maximum 4 evaluates to 5.

We can use an alternate way of expressing this function as a monad.

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 the section Constructing Lists.

maximum 3 ; _4 ==> 3
maximum 3 ; 4 ==> 4

In this definition of maximum, the line ('x' ; 'y') =. y. separates the two items in y. and binds the local name x to the first and y to the second.

Describing Data

So far, data items have been simple nouns such as 2, 3.5 or lists such as 'Hi there'. J allows the definition of lists of numbers by simply separating the numbers by one or more spaces. For example,

l1 =: 1 2 10 _9 3

creates 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 ==> 8

creates a list 8 characters.

Accessing the Parts of Lists

Consider the following definitions:

first =: {.
rest =: }.

Then

first l1 ==> 1
rest l1 ==> 2 10 _9 3
first l2 ==> H
rest l2 ==> i there

Next, consider the definition

from =: {

Then,

0 from l2 ==> H
3 0 2 from l1 ==> _9 1 10

Constructing Lists

As we saw in 1.3.7, we can type in lists as numbers separated by 1 or more spaces or we can type in lists of characters by enclosing them between quote (') characters. We can also build lists by using the append (,) verb.

1 , 2 ==> 1 2
'H','i' ==> Hi
'Hi',' ','there' ==> Hi there
'Hi','there' ==> Hithere

Another 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 ==> 10

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

Then,

1 from l3 ==>
+---+
|0 1|
+---+

open 1 from l3 ==>
0 1

tally open 1 from l3 ==>
2

1 from open 1 from l3 ==>
1

It 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 error

The 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 ; <'hi there' ==>
+-----+--------+
|1 2 3|hi there|
+-----+--------+

List Accessor and Constructor Equations

Given a non empty list x,

(first x) link rest x ==> x

and given two J items a and b:

first a link b ==> a

rest a link b ==> b

Summing the Elements of a Numeric List

As a programming example, we wish to solve the problem of summing the elements of a simple numeric list. To be a bit more precise, we assume that the object given to the verb list_sum which we will define is list and that all elements of the list are numbers. These assumptions will make the solution of this problem a bit simpler.

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 ==> 10

We 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 & 2

display is a helping monad which displays its input on the display console and then returns that input.

traced_list_sum =: monad define
display y.
if. 0 = tally y.
  do. 0
  else. (first y.) + display traced_list_sum rest y.
end.
)

traced_list_sum 1 2 3 4
1 2 3 4
2 3 4
3 4
4

0
4
7
9
10

The J notation provides an abstraction for the above program as:

+/ 1 2 3 4 ==> 10

Computing the Product of the First n Integers

There is a function from mathematics, called factorial, which computes the product of the first n (n >= 0) integers. Using ordinary mathematical notation we can define this function as:

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 ==> 720

As 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 6
6
5
4
3
2
1
0
1
1
2
6
24
120
720

The J notation provides a primitive definition for factorial (!).

!6 ==> 720

The abstraction for the list_sum program could be varied slightly to achieve another solution of the factorial verb as:

*/1 2 3 4 ==> 720

Notice the similarity between the list_sum and factorial verbs.

Exercise

Define a list_product verb. What is the relationship between list_product and factorial?

Comparing Objects

J data objects are considered to be equal if they have the same structure and corresponding elemental values. For singleton objects, the comparison verb is =. For example,

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 1

The match verb (-:) is available to compare structured items.

'Hi there' -: 1 2 ==> 0

The J Vocuabulary

The following table gives the primitive spelling of all J words. Verbs are denoted by normal typeface, giving the monad first, followed by the dyad. Cunjunctions are denoted by bold typeface and adverbs are shown in bold italic typeface.
BARE	DOT	COLON
= Self-Classify - Equal	=. Is (Local)	=: Is (Global)
< Box - Less Than	<. Floor - Lesser of	<: Decrem - Less Or Eq
> Open - Larger Than	>. Ceiling - Larger of	>: Increm - Larg Or Eq
_ Negative Sign /Infinity	_. Indeterminate	_: Infinity
+ Conjugate - Plus	+. Real/Imag - GCD (Or)	+: Double - Not-Or
* Signum - Times	*. Len/Angle - LCM (And)	*: Square - Not-And
- Negate - Minus	-. Not - Less	-: Halve - Match
% Reciprocal - Divided by	%. Matrix Inv - Mat Divide	%: Square Root - Root
^ Exponential - Power	^. Natural Log - Logarithm	^: Power
$ Shape Of - Shape	$.	$: Self-Reference
~ Reflex-Pass-EVOKE	~. Nub	~: Nub Sieve - Not-Eq
| Magnitude - Residue	|. Reverse - Rotate (Shift)	|: Transpose
. Det - Dot Product	.. Even	.: Odd
: Explicit - Monad/Dyad	:. Obverse	:: Adverse
, Ravel - Append	,. Ravel Items - Stitch	,: Itemize - Laminate
; Raze - Link	;. Cut	;: Word formation
# Tally - Copy	#. Base 2 - Base	#: Antibase 2 - Antib
! Factorial - Out Of	!. Fit (Customize)	!: Foreign
/ Insert-Table-INSERT	/. Oblique-Key-APPEND	/: Grade Up - Sort
\ Prefix-Infix-TRAIN	\. Suffix - Outfix	\: Grade Down - Sort
[ Same - Left	[. Lev	[: Cap
] Same - Right	]. Dex	]: Identity
{ Catalogue - From	{. Head - Take	{: Tail
} Item Amend - Amend	}. Behead - Drop	}: Curtail
" Rank - CONSTANT	". Do	": Format
` Tie (Gerund)	`.	`: Evoke Gerund
@ Atop	@. Agenda	@: At
& Bond /Compose	&. Under (Dual)	&: Appose
? Roll - Deal	?. Roll - Deal (fixed seed)	?:
Special Words
a. Alphabet	a: Ace (boxed empty)	A. Atomic Permute
b. Boolean/Basic	c. Characteristic values	C. Cycle-Dir - Perm
D. Derivative	D: Secant Slope	e. Raze In - Memb
E. - Member of Interval	f. Fix	H. Hypergeometric
i. Integer - Index Of	j. Imaginary - Complex	L. L: Level, Level
NB. Comment	o. Pi Times - Circlr	p. Polynomial
p: Prime	q: Prime Factors	r. Angle - Polar
t. Taylor coef	t: Wgtd Taylor Coef	T. Taylor Function
_9: to 9: Constant functions	Constants

A J Programming Example

Suppose we wish to write a J verb which will select the elements of a simple numeric list which are greater than or equal to 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
display y.
if. 0 = tally y.
  do. ''
  else.  if. 0 <: first y.
           do. (first y.) append display traced_select_positive rest y.
           else. display traced_select_positive rest y.
         end.
end.
)

   traced_select_positive 1 2 3
1 2 3
2 3
3


3
2 3
1 2 3

   traced_select_positive 1 _9 2 _3 3
1 _9 2 _3 3
_9 2 _3 3
2 _3 3
_3 3
3


3
3
2 3
2 3
1 2 3

Laboratory Practice

Login to your unix workstation. Next, start up a terminal window by selecting Terminal from the Applications/Accessories menu. Read the manual page for changing a password by entering the following Unix command in the terminal window you have just opened. You must press the enter or return key after each command to cause the command to be executed.

% man yppasswd

Change the password for your new Unix account.

Read the Unix tutorial.

Next, make your own copy of the course files by entering the following Unix commands:

% cp  -r  ~jhowland/j.code.1301/   ~/

% j

Notice that the system prompts you for input with three spaces when you are running J while the unix prompt ends in the "%" character. To exit from J, press the control and D keys at the same time.

Note that when we show a J expression in this document it will be preceeded by three spaces. The prompt characters are printed by J, so you don't type those characters. Similarly, when we show a unix command it will be preceeded by the "%" character.

You should learn to use vi editor from another terminal window. To do this, click the mouse once on the terminal icon on the ToolBar at the bottom of the desktop. After the terminal appears on the desktop, you start the vi editor by typing the command:

% vi

Another possibility, and preferrable to learning vi if you are familiar with simple text editor programs on a Windows or Mac system, is to learn to use the gnotepad+ program. To startup the editor, you should select the gnotepad+ program from the Programs Applicationss menu of the start menu on the toolbar at the bottom of the desktop.

We have installed yet another (easy to use) editor called gedit. To use the gedit program, type

% gedit &

To load any newly created J functions, expressions, etc., enter the J expression:

load 'filename'

Enter the following J function and save it in the file fact.js .

fact =. monad define
if. y. < 2
  do. 1
  else. y. * fact y. - 1
end.
)

Load this new function into J and compute

fact 6
fact 10
fact 100x
fact 200x

Enter the expressions

time'fact 6'
time'fact 10'
time'fact 100x'
time'fact 200x'

so that you can see how much computer time each takes.

Next, consider the following definition:

maximum =: monad define
('x' ; 'y') =. y.
if. x > y
  do. x
  else. y
end.
)

Characterize the behavior of maximum function. Can you construct a maximum function which will compute the maximum value of 3 items?

Try to construct a minimum function and verify, by testing, that it is working correctly.