Home

The Role of Composition in Computer Programming

This paper by Donald McIntyre is a classic in the J language world. It ranks up there with "Why Functional Programming Matters" in terms of concise, impressive examples. Most of the examples have a geometric bent, like finding the area of a polygon. Note that this paper was written using an early version of J, so some of the syntax has unfortunately changed.

By James Hague at 2006-12-19 14:34 | Functional | other blogs | 68819 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Broken link

.com is missing.

J Language

By Jan Van lent at Tue, 2006-12-19 18:24 | login or register to post comments

Fixed.

Thank you for pointing this out.

By James Hague at Tue, 2006-12-19 21:52 | login or register to post comments

Not a good introduction

While this paper is full of examples, I found it not "newbie-friendly"; it assumes the reader is well-aquainted with the APL family of languages, and even not self-contained when it comes to J.

As an example, on the very first page, the author uses the assignment operator =. without a word of explanation, and explains the rank conjunction " with argument 0 as making the function 'appl[y] to the rank-0 cells of its argument' -- rank-0 cells being, as far as I know, a uniquely vector-programming (if not strictly APL) concept. On the other hand, he does explain functions such as -: (halve) and even - (negate); the paper seems undecided about the level of knowledge expected from its readers.

I am posting this note because I was intrigued into reading this paper (actually, into trying to read it) by the comparison with "Why Functional Programming Matters" (WFPM) in the summary; having once, long ago, programmed in APL2 and J, and remembering it favorably, I was looking for an analysis of the sort found in that paper, which might tell me what made that experience special, and what ideas I can use outside of the limited vector-programming context; I found none of that.

To sum, while WFPM is addressing a general programming audience, this paper is pretty much preaching to the vector-programming choir. It is a useful resource if you're already doing it and trying to get better (which, incidentally, is its claimed purpose), but it won't pull you in.

By Shai Berger at Wed, 2006-12-20 08:45 | login or register to post comments

Once upon a time I wrote a J

Once upon a time I wrote a J FAQ. Maybe it is available somewhere (I don't have a copy anymore)...

By Ehud Lamm at Wed, 2006-12-20 09:52 | login or register to post comments

J PRogramming FAQ

J Programming FAQ. The link doesn't have a file extension, but it's just a plain text file.

By Chris Rathman at Wed, 2006-12-20 15:41 | login or register to post comments

Thanks!

It's like finding an old unsent letter in the attic...

By Ehud Lamm at Wed, 2006-12-20 16:07 | login or register to post comments

"Not newbie-friendly" is a

"Not newbie-friendly" is a gross understatement.

I've been trying to learn J off-and-on for a while now to see what the big deal is. I mean, I can see how many problems can be reformulated as vector operations, and get that those can be very fast in certain domains, but I don't see why vector operations are suited for a new language, or what's up with concatenative languages in general.

Anyway, I get a little bit into "Learning J", go off and do something else, and when I come back a few months later have to start at the beginning again because I can't keep the obscure set of symbols straight without jumping back and forth to the dictionary, in which I can't find anything because my brain doesn't have the order of the symbols !@#$%^&*<> memorized as it does the alphabet. I can't even parse a line (in terms of being able to tell where one could insert parentheses without changing anything) without knowing which of the symbols are single character verbs, which are multi-character verbs, which are adverbs, conjunctions, etc. Understanding the basic grammar of the language seems to depend on deep knowledge of all the built-ins, of which there are legion. (at least, it seems that way from my vantage point)

What on earth is it about J/APL that requires such difficult-to-remember built-in operations? I feel like I'm back in Japanese class trying to remember kanji, only without the added benefit of being able to guess something of an unfamiliar figure's purpose from its position in the sentence.

By fizbin at Wed, 2006-12-20 18:04 | login or register to post comments

I also find incomprehensible

I also find incomprehensible the drive to brevity at the expense of readability in that community. For example, instead of sin(x), cos(x), tan(x), sqrt(x), etc., in J they are respectively 1 o. x, 2 o. x, 3 o. x, 4 o. x, etc. Why? What is the point of that?

I took a month to learn J and it was kinda neat while I remembered it, but it only took a few days for it to slip away.

By James McCartney at Wed, 2006-12-20 18:31 | login or register to post comments

Personally, I think the

Personally, I think the apporach in APL and J is not a sweet spot in terms of language design. I prefer longer names, standard control structures (which J added) etc. Still, if you want to understand how this became the preferred style you need to go back to the history of this family of languages. APL's choices may have made more sense, since the operators each had a unique (and somewhat mnemonic) glyph.

It's worth keeping in mind that not only are hte builin operators so short, the preffered programming style is often to use very dense loopless code. This may alos be seen as choosing brevity at the expense of readability.

By Ehud Lamm at Wed, 2006-12-20 20:34 | login or register to post comments

The drive to brevity...

...is coming from mathematics where single character symbols are the norm. Most mathematicians would rather break into a bizarre new font, or heavily overload existing symbols, than use a multi-letter variable name - except for the names of trig functions and one or two other operators.

For example the reduction of Maxwell's equations to a trivial looking pair of equations relating differential forms is seen as a triumph despite the fact that it overloads the symbols d and * which have countless other uses. The modern form aids both readability and writability.

I think it would be interesting to try to understand better why this is desired in mathematics, but not in programming languages. Even computer science texts often use the conventions of mathematics in their mathematical sections.

By sigfpe at Thu, 2006-12-21 00:17 | login or register to post comments

My guess

I think it's a (mental) symbol table issue. A typical math paper may not exhaust the Greek alphabet. The bananas paper introduced only a few funky symbols iirc. But computer programs have so many symbols that we had to invent hierarchical namespaces, let alone multicharacter symbol names.

4 o. x above is a bad symbol when the table is large. To simplify lookup, symbols must be somehow syntactically associated with what they refer to like sqrt refers to square root without actually spelling it out. I go crazy while reading code where variables are in French or Chinese despite comments in English.

By Koray Can at Thu, 2006-12-21 01:54 | login or register to post comments

I remind y'all of Iverson's

I remind y'all of Iverson's Notation as a Tool of Thought. The very title tells you something about the origins of the APL notation.

By Ehud Lamm at Thu, 2006-12-21 08:46 | login or register to post comments

Math-style notation

Note too that math texts often use beautiful two-dimensionalish typesetting (a la TeX) and variable-size symbols (like capital sigma for sum, capital pi for product, giant Ss for integrals, etc.).

Perhaps this is why Knuth found it pleasant to typeset a program "for reading" as in his literate programming work on WEB/CWEB.

What if we had nice symbols for fold, map, call/cc...? Surely someone has tried this..?

But I doubt anyone wants to be programming in TeX. Maybe we could use an editor like TeXmacs to facilitate this.

Note that C (and many others) already use and/or overload ~ & ^ | % ! ? : ; , \ " ' and of course the mathematical + - * / < > =, and a few two-character symbols += &= != ... || &&.

And this actually includes every single-character symbol on the standard keyboard except @ # ` . _ $ (the former of which ObjectiveC uses, and I believe the latter used to be allowed in C identifiers).

[edit: added more symbols]

By dbfaken at Thu, 2006-12-21 13:38 | login or register to post comments

A lot depends on context of use

I think it would be interesting to try to understand better why this is desired in mathematics, but not in programming languages. Even computer science texts often use the conventions of mathematics in their mathematical sections.

I think Koray is on the right track.

For proofs, you are trying to distill a very focused but very laborious chain of thoughts into a pithy understanding. Since you take it for granted that a proof will require a very careful reading, and will be limited in length, you can assume that the reader has already "loaded the context" through the very act of reading the proof.

By contrast, code often comes in very large, multi-context, cross-referenced projects that can't possibly be held in their entirety in your head, so adding more contextual information in the notation itself is vital.

I take it for granted that I might spend an hour reading and understanding a page-long proof; if I can't understand a page of code (out of a large project) in a few minutes, it needs to be rewritten .

By Marc Hamann at Thu, 2006-12-21 15:23 | login or register to post comments

Spec#

I think there's a paper comparing Spec# (or AsmL, can't find the paper just now) and C#, and the only-a-little-bit more verbose specification language was super easy to read, I really liked it. Along with things like ACE I dream of a slightly more (English) natural-languagy syntax. I think it could be one of those things that doesn't seem like a big difference at first, but in the long run (maintenance!) would pay nice dividends. Diving into some big but new-to-you codebase is hard.

By raould at Thu, 2006-12-21 18:10 | login or register to post comments

Maybe you've answered me but not the way you think

By contrast, code often comes in very large, multi-context, cross-referenced projects that can't possibly be held in their entirety in your head, so adding more contextual information in the notation itself is vital.

Mathematics has similar issues and I'm not sure people keep all that much material in their heads. A textbook may have many cross-references (including future references) and 'import' theorems from a wide variety of sources. It hadn't really dawned on me before, but mathematical texts are quite modular. Despite there being many derivation steps in a text, only certain of these derivations are 'exported' into the 'global namespace' in the sense that they are labelled as theorems (or lemmas or corollaries). Very occasionally you'll see something that breaks modularity like "using the first paragraph of the proof of X we can deduce...". All of this is similar to how we make programs readable.

if I can't understand a page of code (out of a large project) in a few minutes, it needs to be rewritten

Maybe the difference is this: it's really important to be able to dive into someone else's project and make approximate sense of it immediately. Mathematics texts, on the other hand, are designed to be read somewhat linearly, and when a section is to be read, some knowledge of the entire contents of the book up to that point, is often assumed as a prerequisite.

By sigfpe at Thu, 2006-12-21 19:35 | login or register to post comments

The unasked question here

The unasked question here seems to be: Is mathematical syntax good for mathematics? Perhaps its just a question of mathematic being older and the syntax to established to be changed. I sure think math would be easier if all equations looked like Haskell or something instead of mess of strange unpronouncable symbols put together by obscure precedence rules.

By Felicia Li Svilling at Thu, 2006-12-21 19:45 | login or register to post comments

Mth z trs

Is mathematical syntax good for mathematics?

Having spent a long time getting used to it, I now can't help saying yes. ;-)

I have come across some notations that obscured more than they illuminated, but in general there is something about the level of abstraction and complexity of ideas in math that makes it well suited to pithy notations.

And, unlike programs, proofs don't have to run, just convince other math wonks. ;-)

By Marc Hamann at Thu, 2006-12-21 20:47 | login or register to post comments

Remember - math uses natural

Remember - math uses natural language as well. Hardly any proof sticks to using logic symbols (except the logic buffs), but use normal language using terms for concepts and describe connections between concepts that are not laid down in equation form, or would be too cumbersome to do so.

Try writing down a proof of the pythagorus theorem using standard mathematical symbols only. Even that humble piece of genius will be rendered incomprehensible as you struggle to express "a right angled triangle".

By Srikumar Subramanian at Fri, 2006-12-22 02:19 | login or register to post comments

Even further than down the linear road

Mathematics texts, on the other hand, are designed to be read somewhat linearly, and when a section is to be read, some knowledge of the entire contents of the book up to that point, is often assumed as a prerequisite.

Upon further reflection, I think this hits on the heart of the matter much better than my first thought, and I would take it a step further than the context of a textbook: the whole field often assumes some previous work spent understanding pre-requisite ideas.

Programs tend to assume that, aside from some standard library objects, each program creates a unique context that can't be "shorthanded". By contrast, math assumes much more that a particular piece of work takes part in a pre-established shared environment of ideas, notations, etc.

I think it is more this that I meant by "keeping context in your head" than the specifics of a complicated proof or chain of proofs.

By Marc Hamann at Thu, 2006-12-21 20:41 | login or register to post comments

Mathematical notation

To start, there is no excuse for 4 o. x or at least none that can be reasonably derived from mathematical notation.

However, some of the forces driving the choices made in mathematical notation are shared with naming conventions and such in (some) programming languages. Certainly, brevity is an one example.

Another is simply that there are not always meaningful names. This comes up in polymorphic code a lot, hence Haskellers' fondness of single character names. Combined with the guideline that more locally scoped variables need less descriptive names, I do not find much (anything) gained in writing map (x:xs) = ... as say map (firstItem:restOfTheItems) = ... or map (item:items) = ... especially combined with community wide naming conventions.

Similarly with overloading. Mathematicians only mildly truly overload symbols and then rarely in a way that can be ambiguous. Usually, the overloading is far more systematic and revealing; much akin to Haskell type classes or polytypic programming or J's matrix liftings.

More widespread, the use of different fonts in mathematics also has it's counterpart in coding conventions. Everytime I've seen mathematicians use multiple fonts, each font represented a different type of object. The obvious correspondence in code is prefixing and such (e.g. m_ in C++, Hungarian notation, ! in Scheme, leading caps for constructors and types in Haskell, etc.)

For example the reduction of Maxwell's equations to a trivial looking pair of equations relating differential forms is seen as a triumph despite the fact that it overloads the symbols d and * which have countless other uses. The modern form aids both readability and writability.

I prefer ∇F=J, but the primary reason this is seen as a triumph (especially with reference to the version I gave) is that it is more structured (/reveals more structure in the problem) and (in my version at least) is a heck of a lot more manipulable. These, again, exist in code, e.g. iteration combinators such Haskell's map or most of J's operators or more directly the use of records/objects. Writing code this way more clearly reveals it structure and is more amenable to manipulation (e.g. algebras of combinators).

I think it would be interesting to try to understand better why this is desired in mathematics, but not in programming languages.

Scratching just slightly beyond the surface reveals that it is both desired and present in programming languages.

By Derek Elkins at Tue, 2006-12-26 10:03 | login or register to post comments

Mathematicians only mildly truly overload symbols

Actually, I think they overload incredibly heavily, relying on context to help disambiguation. Pick up an algebra book and count the ways abuttal is used. This is partly mitigated by a trick mathematicians employ: (implicitly) using ambiguous grammars with the property that whichever parsing and disambiguation you adopt, the value of the entire expression remains unchanged (modulo something meaningful). Actually, this is something I've often wanted to be able to do in a programming language: make some kind of promise to the compiler that it's free to choose any reasonable parsing/interpretation of certain symbols it wants in expressions.

By sigfpe at Tue, 2007-01-02 22:23 | login or register to post comments

playing by the rules

if you are willing to pick one of the reasonable parsing/interpretations of certain expressions (just because the final values are equivalent doesn't mean we can't try to pick a faster/smaller path to generate them) then Haskell rewrite rules might be a way to make that kind of promise.

(or at least that's what Peyton Jones, Tolmach, and Hoare say in "Playing by the Rules: Rewriting as a practical optimisation technique in GHC")

By Dave at Thu, 2007-01-04 08:50 | login or register to post comments

Origins of sin(x), cos(x), etc in J

For example, instead of sin(x), cos(x), tan(x), sqrt(x), etc., in J they are respectively 1 o. x, 2 o. x, 3 o. x, 4 o. x, etc. Why? What is the point of that?

I found an answer to this while reading A personal view of APL that skipcave had linked to. The quotation below starts on page 4:

Functions were first adopted in the forms found in elementary mathematics, having one argument (as in |b| and -b) or two (as in a+b and a-b). In particular, each had an explicit result, so that functions could be articulated to form sentences, as in |a-b| ÷ (a+b).

In mathematics, the symbol - is used to denote both the dyadic function subtraction (as in a-b) and the monadic function negation (as in -b). This ambivalent use of symbols was exploited systematically (as in ÷ for both division and reciprocal, and * for both power and exponential) to provide mnemonic links between related functions, and to economize on symbols.

The same motivations led us to adopt E. E. McDonnell's proposal to treat the monadic trigonometric (or circular) functions and related hyperbolic and pythagorean functions as a single family of dyadic functions, denoted by a circle. Thus sine y and cosine y are denoted by 1oy and 2oy, the numeric left argument being chosen so that its parity (even or odd) agrees with the parity of the function denoted, and so that a negative integer denotes the function inverse to that denoted by the corresponding positive integer. This scheme was a matter of following (with rather less justification) the important mathematical notion of treating the monadic functions square, cube, square root, etc. as special cases of the single dyadic power function.

So there's a method to the madness, at least :)

By Jeff Nowakowski at Thu, 2006-12-28 11:24 | login or register to post comments

Focusing on the "wrong" things

Sure, the syntax of J (and APL) is terse to the point of obscurity, something Perl also is guilty of.

However, the genius of APL/J is the set of combinators available, and their semantics. They figured out, long before others, a small set of key highly polymorphic combinators in terms of which most everything else can be expressed. And they do it for vectors/matrices instead of dealing with the less natural inductive types (less natural from a basic mathematical point of view).

The kind of polymorphism available in APL/J is only rivaled by that in LISP/Scheme. ML and Haskell showed how to tame (most of) the polymorphism of LISP into something trustable. The only work that I am aware of that even comes close to typing some of APL/J is 's FISh. Even though he calls bondi FISh 2.0, that seems to be a really different language as it focuses way more on (really neat!) ideas on pattern-matching rather than on pursuing various ideas of shape-polymorphism.

Even though I am a big fan of SYB, that does not even get close to touching shape polymorphism the way that say the Matrix Template Library does (and I am no fan of C++ !).

By Jacques Carette at Thu, 2006-12-21 00:24 | login or register to post comments

They figured out, long

They figured out, long before others, a small set of key highly polymorphic combinators in terms of which most everything else can be expressed.
I keep thinking I should learn J or K, but the terseness/operator-overloading/different-terminology(gerunds?)/hard-to-parse-in-my-mind factor has kept it on the back burner. Maybe someone familiar with a vector language could translate one or two of their favorite examples into a more 'conventional' language like lisp. Here's my interpretation of a few of the operators from the beginning of the paper. 
;;; atop
(defun @ (g h)
  (lambda (&rest xy) (funcall g (apply h xy))))
 
;;; with/bond
(defun & (g h)
  (lambda (&rest xy) (apply g (mapcar h xy)))) 

;;; hook
(defun hook (g h)
  (lambda (x &optional (y nil y?)) 
    (if y? 
        (funcall g x (funcall h y))
        (funcall g x (funcall h x)))))

;;; fork
;;; Haskell alert: Looks a lot like liftM2 in the (->) monad.
;;; liftM2 (+) sqrt (\x->x*x) 4  ==> 18
(defun fork (f &rest gh)
  (lambda (&rest xy) 
    (apply f (mapcar (lambda (fun) (apply fun xy)) gh))))

;;; oblique
(defun /. (funs arg)
  (map (type-of funs) (lambda (f) (funcall f arg)) funs))

(defun sqr (x) (* x x))

(defun tests-pass? ()
  (and
    (equalp (map 'vector (@ #'1+ #'sqr) #(1 2 3))
            #(2 5 10))
    (equalp (map 'vector (@ #'1+ #'*) #(1 2 3) #(4 5 6))
            #(5 11 19))
    (equalp (funcall (& #'+ #'sqr) 2 10)
            104)
    (equalp (funcall (& #'+ #'sqr) 2)
            4)
    (equalp (funcall (fork #'+ #'sqr #'sqrt) 4)
            18)
    (equalp (funcall (fork #'+ #'* #'/) 2 3)
            20/3)
    (equalp (funcall (hook #'* #'-) 2 10)
            -20)
    (equalp (funcall (hook #'* #'-) 2)
            -4)
    (equalp (/. #(sqr sqrt) 9)
            #(81 3))))
And they do it for vectors/matrices instead of dealing with the less natural inductive types (less natural from a basic mathematical point of view).
I'd be interested in reading more about this. Recommend any good papers?
By Greg Buchholz at Thu, 2006-12-21 18:03 | login or register to post comments

Wish I could

And they do it for vectors/matrices instead of dealing with the less natural inductive types (less natural from a basic mathematical point of view).

I'd be interested in reading more about this. Recommend any good papers?

Really wish I could - I am still looking for them myself. It appears that Arrays/Vectors/Matrices are never really "first class" in any of the theoretical work in functional programming circles. Of course, most languages are forced to implement them anyways.

Take a look at the FISh papers (linked in my parent post) for a good attempt at dealing with arrays more naturally. Otherwise the only work I know of is either buried in heaps of C++ templates (like MTL and Boost), or deep in research compilers for things like parallel Fortran. I really recommend the book Advanced Symbolic Analysis for Compilers.

By Jacques Carette at Fri, 2006-12-22 15:23 | login or register to post comments

Arrays and matrices as "first-class" objects

Although general purpose languages tend to eschew arrays and matrices as
primitive objects, dialects and languages that target vector or parallel machines often have constructs that use them as such. Examples include Sisal and Lisp and Fortran dialects for the old Connection Machines.

Another place where vectors and matrices are often found as primitive objects is in DSLs. Matlab is probably the most widely used example, though I would assume that the underlying languages for many CAD systems would have these primitives, as well. Also, Symbolic math packages like Macsyma and Mathematica also have these objects.

There's a real question about how far one goes in turning mathematical objects into programming language primitives. Bignums are one level, inclusion of Rationals and Complex another. Would one want to add Quaternions and Octonians? How about modular arithmetic? As far as structures go, should you stop with Vectors through rank-k Tensors (for some k), or do you want to bite the bullet and subclass these from more basic mathematical structures as groups, rings, and fields?
And what about functional objects? You can look at a vector as a function I->X (for some set X). And once you go there and start looking at things as functions, do you go on to add differentiation and integration to the mix? Do you start adding Borel sets and distributions? How about new structures like fuzzy sets?

In the final analysis, language designers (and compiler writers) have limited resources. They need to have a "rich enough" set of primitives that a target programmer will be able to use fruitfully. Other, more esoteric features tend to get relegated to the boutique languages for people who need them, simply because the time that would be spent in putting these into a general purpose language is probably better spent trying to improve the speed of the compiler or in writing a library for these items. Although it does raise one question - if your language is defined such that using library abstractions is more painful than using built-in operators, are your libraries (or their invocation) designed correctly?

By fadrian at Fri, 2006-12-22 16:55 | login or register to post comments

More Info on J

Iverson originally developed APL (initially called Iverson notation) as a notation for describing algorithms. It was NOT intended as a computer language. Iverson felt that traditional math notation was ambiguous, so he designed a symbolic notation that would have unambiguous meaning for any written example.

If you are interested in the rationale for the development of APL (and J, K, Nial, and other symbolic languages), you should read the transcript of Iversons' Turing Award lecture from 1979. The lecture is entitled "Notation as a Tool of Thought", so that gives you a hint as to its theme:
http://www.acm.org/awards/article/a1979-iverson

To get a flavor of Ken's lecture, here are some quotes from the transcript:

>
Mathematical notation provides perhaps the best-known and best developed example of language used consciously as a tool of thought. Recognition of the important role of notation in mathematics is clear from the quotations from mathematicians given in Cajori's A History of Mathematical Notations [2, pp. 332, 331]. They are well worth reading in full, but the following excerpts suggest the tone:

By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems, and in effect increases the mental power of the race.
A. N. Whitehead

The quantity of meaning compressed into small space by algebraic signs, is another circumstance that facilitates the reasonings we are accustomed to carry on by their aid.
Charles Babbage
>

Iverson felt that a consistent, unambiguous notation was the optimum way to describe complex algorithms or processes, and he felt traditional mathematic notation was both ambiguous and inconsistent. However, as a general rule, any unambiguous notation should be capable of being implemented as a computer language. Iverson took to the idea of converting his notation to a programming language (called APL for A Programming Language), and spent the rest of his life polishing and improving the notation and the computer language.

Generally, because of it's power, J can express most algorithms in the fewest symbols of any notation. In addition, continual improvements are being made in the computational efficiencies of the various primitive functions of the language. As a simple example, the primitive sort in J (expressed as /: which is considered a single symbol) will select the most efficient sort algorthm, depending on the data being sorted.

For more insight into the language, Iverson's paper "A personal View of APL" shows his thoughts while developing the original symbolic language:
http://www.research.ibm.com/journal/sj/304/ibmsj3004O.pdf

Iverson notation was used to design the architecture of the IBM 360 computer.

After nearly 30 years of work on symbolic notation using specialized symbols and keyboards for APL (and getting much flack for using non-ASCII symbols), Iverson re-designed the language. He made many improvements to the notation, gleaned from years of analysis and discussion with the programming community. In addition, he replaced the special APL symbols required by APL with all-ASCII symbols. The new language (Iverson liked to call it a dialect of APL) was named "J" for obscure reasons.

Iverson and his collaborator Roger Hui, defined about 120 symbols in J for primitive functions. Each symbol used an ASCII symbol either alone, or followed by a period or colon. The J symbol vocabulary is here:
http://www.jsoftware.com/help/dictionary/vocabul.htm

The hyperlinked definitions of each symbol are defined in a rigorous and extremely concise format. However that format is difficult to comprehend without a key to the layout. These concise definitions are described in the J language itself, so the definitions are more for reference for the experienced J programmer than an educational tool.

A J vocabulary with some helpful hints fits nicely on one 2-sided page (cheat sheet) when formatted correctly. See:
http://elliscave.com/APL_J/Jrefcardv601.pdf

Luckily, there are many expository texts which are much better for learning the basics of J than the vocabulary:
http://www.jsoftware.com/jwiki/Books

I would recommend "J for C Programmers", or "Learning J" as excellent educational texts for the general programmer wanting to learn J.

Iverson intended that the 120 symbols in J should represent a set of functions that would cover the majority of basic operations found in most algorithms. Many of J's primitives would be library functions in other languages (sort, matrix invert, insert, scan, etc.). J has it's own set of library functions called "phrases" which cover a much wider ground.

J primitives all have a consistent, uniform interface structure. This makes construction of complex algorithms simply a matter of placing the primitives next to each other on a line. Execution precedence was always from right to left (except when overridden by parenthesis), so there is no memorizing precedence rules (which would be tough, with 120 functions).

Since most algorithms and computer programs represent repetitive operations on sets of numbers or characters, all of J's functions operate on either single or multiple arguments. Arguments can be vectors, matrices, or collections of disparate items. Thus, most repetitive algorithms are represented in J with a few symbols on a few lines (and few, if any, control statements). Iterative or repetitive operations are implied, thus saving the programmer the details of indexing and looping. Each primitive extends its functionality to vectors and matrices in a consistent and rigorous manner. Once one masters the rank extension concepts for primitives ( a non-trivial exercise), all of the language's functionality begins to fall into place.

Unlike many computer languages, memorizing all of the primitives in J is not a simple matter. With 120 primitives, some of which are fairly esoteric mathematical functions, such an approach has a very steep learning curve. Luckily, there are 30 or so primitives that make up the most commonly used functions, and those can be absorbed with a few days of study. Other primitives can be explored when the need arises. In addition to the primitives, Some unusual concepts (rank, hooks, forks) need to be understood to fully grasp the language. Luckily, there are many good references that make coming up to speed in J a reasonably comfortable (and sometimes fun) process. Again see:
http://www.jsoftware.com/jwiki/Books

While J can be used for any general-purpose programming task, it is especially useful for exploring various algorithmic approaches to a problem. J's concise, powerful notation and interpretive nature promotes iterative exploration techniques that are more difficult in other languages. However, J's marked differences from other common programming languages makes it difficult to use on a casual basis, as it's unusual (but rigorously consistent) syntax is hard to keep in the mind's cache after working with more common scalar languages.

For some more insight, here is the forward of Henry Rich's book "J for C Programmers"

>
You are an experienced C programmer who has heard about J, and you think you'd like to see what it's all about. Congratulations! You have made a decision that will change your programming life, if only you see it through. The purpose of this book is to help you do that.

It won't be easy, and it certainly won't be what you're expecting. You've learned languages before, and you know the drill: find out how variables are declared, learn the syntax for conditionals and loops, learn how to call a function, get a couple of examples to edit, and you're a coder. Fuggeddaboutit! In J, there are no declarations, seldom will you see a loop, and conditionals often go incognito. As for coding from examples, well, most of our examples are only a couple of lines of code—you won't get much momentum from that! You're just going to have to grit your teeth and learn a completely new way to
write programs.

Why should you bother? To begin with, for the productivity. J programs are usually a fifth to a tenth as long as corresponding C programs, and along with that economy of expression comes coding speed. Next, for the programming environment: J is an interpreted language, so your programs will never crash, you can modify code while it's running, you don't have to deal with makefiles and linking, and you can test your code simply by entering it at the keyboard and seeing what it does.

If you stick with it, J won't just help the way you code, it'll help the way you think. C is a computer language; it lets you control the things the computer does. J is a language of computation: it lets you describe what needs to be done without getting bogged down in details (but in those details, the efficiency of its algorithms is extraordinary). Because J expressions deal with large blocks of data, you will stop thinking of individual numbers and start thinking at a larger scale. Confronted with a problem, you will immediately break it down into pieces of the proper size and express the solution in J—and if you can express the problem, you have a J program, and your problem is solved.

Unfortunately, it seems to be the case that the more experience you have as a C programmer, the less likely you are to switch to J. This may not be because prolonged exposure to C code limits your vision and contracts the scope of your thinking to the size of a 32-bit word — though studies to check that are still under way and it might be wise for you to stop before it's too late — but because the better you are at C, the more you have to lose by switching to J. You have developed a number of coding habits: for example, how to manage loops to avoid errors at extreme cases; how to manage pointers effectively; how to use type-checking to avoid errors. None of that will be applicable to
J. J will take advantage of your skill in grasping the essence of a problem—indeed, it will develop that skill considerably by making it easier for you to express what you grasp—but you will go through a period during which it will seem like it takes forever to get things done.

During that period, please remember that to justify your choice of J, you don't have to be as expert in J as you were in C; you only have to be more productive in J than you were in C. That might well happen within a month. After you have fully learned J, it will usually be your first choice for describing a program.

Becoming a J programmer doesn't mean you'll have to give up C completely; every language has its place. In the cases where you want to write code in C (either to use a library you have in C or to write a DLL for a function that is inefficiently computed in J),
you will find interfacing J to DLLs to be simple and effective.

This book's goal is to explain rudimentary J using language familiar to a C programmer. After you finish reading it, you should do yourself the honor of carefully reading the J Dictionary, in which you can learn the full language, one of the great creations in computer science and mathematics.
>

Ken Iverson passed away in 2004. Vector, the British APL Journal, devoted a full issue to his life and work:
http://vector.org.uk/archive/v223/

By skipcave at Sun, 2006-12-24 10:49 | login or register to post comments

An introduction to J for Haskell, ML, or Scheme programmers?

I would recommend "J for C Programmers"

Generally, because of it's power, J can express most algorithms in the fewest symbols of any notation.

Do you know of any paper or article which compares/contrasts the power of J with languages like Haskell, ML, Scheme, etc? Or do you know of any equivalent of an introduction to J for Haskell, ML, or Scheme programmers?

By Greg Buchholz at Thu, 2006-12-28 02:00 | login or register to post comments

J for Haskell Programmers

There aren't very many texts comparing APL/J with scalar languages, as it would be like comparing apples to oranges. J usually deals with a whole dataset at once, while most other scalar languages deal with one item in the dataset at a time. Although the book "J for C programmers" is supposedly for C programmers, it could have easily been entitled "J for scalar programmers", as it really covers that mental leap that one needs to take when moving to a symbolic matrix language from almost any other language.

By skipcave at Tue, 2009-04-07 22:59 | login or register to post comments

Hehner's Universal Algebra

Today I was looking through E. C. R. Hehner's publications and I was struck by the similarity in spirit between his universal algebra and APL. But he doesn't cite Iverson in his work, so maybe it was just parallel development.

One elegant thing the universal algebra adds is true and false (or ⊤ and ⊥ if those display correctly) as plus and minus infinity. See the two short papers From Boolean Algebra to Unified Algebra and Unified Algebra for details. He has a whole textbook A Practical Theory of Programming (mentioned a couple of times on LtU) written in his idiosyncratic notation.

By kenhirsch at Wed, 2007-01-03 20:55 | login or register to post comments

The Terseness of J

There is often discussions about the "terseness" of J, and how that makes it hard to read and understand. In reality, terseness has nothing to do with readability or understandability. Chinese ideograms provide one symbol for each complete word or concept in the language, much like J or APL. Chinese text is extremely "terse" when compared to English, but I'm sure if you told a native Chinese that their language is harder to read and understand than English because it is too terse, they would disagree.

Readability/understandability of any text is simply a function of familiarity, not terseness. The reason that common programming languages are "readable" to many programmers, is because one language will often use constructs that are similar to other languages, which the reader is already familiar with. The reason that J seems hard to read is because the reader doesn't understand the language, not because the language uses fewer symbols. J sacrificed similarity with scalar languages for the higher goal of a simple, consistent, precise, executable notation.

A similar argument can be made for comments. If the reader is very familiar with a specific programming language, well-written code in that language will self-describe its' processes to that reader. Of course, code can be written to disguise its function, and poorly-written code can still be difficult to read. Comments are still useful for readers who are not proficient with a specific language, but who must maintain that unfamiliar code.

J symbols can easily be assigned English words, just as mathematical symbols can be assigned words. For example, take the mathematical equation x = y ^ 2 + 3 * z

One can write this this in pure English as: "x equals y squared plus three times z" However, this is not typically done, because the result is more verbose than necessary.

This is even more true with J. Take the J expression to calculate the average of a group of numbers (the expression "NB." precedes a comment):

avg =. +/ % #
avg 45 66 35 86 24
51.2
avg i. 100 NB. Find the avg of the number sequence from 0 to 99
49.5

For "clarity", one could assign each J symbol or expression an English name:

sum_up_all_numbers =. +/
divide_by =. %
count_the_number_of_numbers =. #

Now we can write our J function in English words (spaces separate the functions):

avg1 =. sum_up_all_numbers divide_by count_the_number_of_numbers
avg1 45 66 35 86 24
51.2
avg1 i. 100 NB. Find the avg of the number sequence from 0 to 99
49.5

For someone not familiar with J, the English word approach may be easier to read. However, a typical J programmer would never do this, because it would require too much typing. Anyone marginally familiar with J symbols would immediately grasp the original code much quicker than the English translation. The correct form for J programs is to use the primitive J symbols, which will make the resulting code terse. For J programmers the terse form is much easier to read than an English-substitute version.

The issue here is: Just how far should the J programmer go towards expanding an elegant J expression into a verbose English translation, in order to help other programmers understand what is going on? In my opinion, not very far. The whole purpose of an efficient notation is to allow a complex algorithm to be defined in a simple, concise way that can be scanned and understood in a single glance.

It is true that this kind of proficiency in reading J code is not obtained overnight. However when one becomes proficient with J, you discover that you can deal with complex processes as a whole, that were not possible before you learned J. The notation you use to describe a problem shapes the way you think about the solution. J will change the way you think, and change how you approach the solution to problems. Whether this is good or bad depends on your viewpoint. Reference - Notation as a Tool of Thought (Iverson)

By skipcave at Thu, 2010-02-18 23:30 | login or register to post comments

Simple ray tracer...

...in K.
By Greg Buchholz at Fri, 2010-02-19 01:25 | login or register to post comments