CHAPTER 20


		    NEW PROGRAMMING LANGUAGES AND ICL


20.1
ICL And New Programming Languages

	  You can instruct the computer to do only what you can express in the
	  programming language.	 The choice of programming language can be
	  crucial.	With general language processing techniques like ours, one
	  can make new languages with ease.

	  One constructs a new language by contributing individual rules of
	  grammar.	Each rule of grammar introduces a specific notation that
	  represents some human concept.  Generally, you start with an initial
	  set of rules which support notations that you know you'll need.
	Additional notations, represented by new rules of grammar, may be
	contributed as time passes, as simpler notations for heavily used
	idioms are recognized, or as entirely new capabilities are required.

	ICL is a programming language so constructed.  ICL should serve as a
	good example for many programming languages in general.  ICL is real;
	it has been in continuous use since 1977, at the California
	Institute Of Technology and/or University Of Southern
	California/Information Sciences Institute, and more recently at an
	adjency of the federal government.


20.1.1
Strongly Typed Like PASCAL

	Besides introducing new syntax, a programming language has some well
	defined semantic properties as well.  For example, ICL is a ~strongly
	~typed language, because any value is an ~instance of some ~datatype.
	Data which are instances of distinct types can never be confused in a
	strongly typed language.

	Examples of types are INTeger numbers, numbers with fractions (REALs)
	and names.  While data of distinct types can certainly be associated
	together, data of one type should not be ~confused with data of
	another type.  One cannot be delivered where the other is expected, in
	a strongly typed language.

	ICL is like PASCAL in being strongly typed.  Unfortunately, PASCAL's
	  type-checking breaks down at variants, and elsewhere due to the
	  possibility of managing memory incorrectly (Chapter 31).


20.1.2
Memory Management Like LISP

	  The correct management of memory is enforced in ICL, as it is in the
	  programming language LISP.	Both languages guarantee error-free
	  memory management by providing ~no notations to allocate or deallocate
	  memory.  Memory allocation occurs implicitly, as part of the meaning
	  of notations that form new data.	Deallocation occurs automatically,
	  by a method called ~garbage ~collection (Part 8).


20.1.3
Polymorphism Like ADA

	  ICL and ADA are alike in that both support user-defined ~polymorphism
	  or ~overloading.  It is possible to define more than one function by
	  the same name.	The advantage is the ability to use (much) fewer names
	  overall.

	  A large set of functions can be called via a small set of
	  names.  For example, the name ABS can be used to denote both the
	  ~absolute ~value of an integer and also of a REAL number.	 In FORTRAN,
	  where user-defined polymorphism is ~not supported, one must use the
	  name ABS when dealing with REALs, and the distinct name IABS when
	  dealing with integers.


20.1.4
Coercions

	  ICL, unlike the other languages, supports user-defined ~coercions.
	  Coercions allow you to specify how data of one type can be converted to
	  data of another type.	 Such conversions will happen when needed, ~and
	  ~the ~programmer ~doesn't ~have ~to ~specify ~where ~they're ~needed!

	  These implicit conversions support large program modification with
	  remarkable ease.  (A big example appears in Section 23.5.3.2).

	  This resolution or inferencing of where to apply what coercions occurs
	  at compile-time (when your program specification is introduced to the
	  computer) and not at run-time, and hence you pay no execution overhead
	  for these linguistic conveniences.


20.1.5
Disk-Resident Data

	  ICL also integrates disk-resident data with data in main memory.
	  There is automatic swapping of data to and from the disk.	 Swapping
	  is based on semantic entities and not on pages of memory.	 Even for
	  very large databases, fast garbage collections are achieved by
	  concentrating only on data in main memory (Chapter 33).

	  ICL is distinguished not only in its semantics, but also by its
	  reasonably rich syntax.  As you read thru the following, you will find
	  some usual notations and some less usual but very useful and fun
	  notations.



20.2
Basic Parts Of A Language:  Expressions, Statements, Quantifiers, And
				    Declarations

	  Programming involves the calculation of values, e.g.,
	  numbers, and the control of how the computed values interact so as to
	  achieve a desired goal.


20.2.1
Expressions And Statements

	  To aid in instructing the computer, high-level languages have at least
	  two categories of notations, one for expressing values, such as "1+2",
	  and one for specifying what to ~do with values.  We will denote the
	  first category with the name EXPR, short for EXPRession.

	  The other category, called STATEMENT, denotes actions, like the
	  assignment of a value into a variable, or producing output or
	  consuming input.  STATEMENTs, unlike EXPRs, do not themselves denote
	  values.

	  An example of both an EXPR and a STATEMENT follows:

		    TWO_PI :=  2 * 3.141592 ;

	  As a whole, this is a STATEMENT.	It computes a value and puts it
	  into a variable, TWO_PI.  The part that computes a value, "2*3.141592"
	  is an EXPR.


20.2.2
New Rules To Capture New Notations

	  In inventing a new programming language, we can make this notation
	  admissable, and call it a STATEMENT by including the following rule
	  of grammer:

		    <ID>  :=  <EXPR>  ;			->	  <STATEMENT>

	  The ID (short for IDentifier) denotes a variable, TWO_PI in our
	  example.	ID is another syntactic category, besides EXPR and
	  STATEMENT, which means "any name", like TWO_PI.

	  Another rule of grammar allows numbers to be admitted as EXPRs:

		    <NUMBER>		    ->	<EXPR>

	  Thus each of "2" and "3.141592" is an EXPR.

	  EXPRs may be combined, via another rule of grammar:

		    <EXPR>	*  <EXPR>			->	  <EXPR>

	  We have now introduced enough rules to render our original assigment
	  into TWO_PI as a valid STATEMENT.



20.2.3
Quantifiers

	  Beyond EXPRs and STATEMENTs, another syntactic category, called
	  QUANTIFIER, denotes notations that cause repetition.  It may be
	  desirable to repeat a computation more than once.  A QUANTIFIER causes
	  ~iterations, and a computation may be executed ~once ~per ~iteration.

	  For example, a QUANTIFIER may be formed by the rule:

		    repeat	<EXPR>  ;			->	  <QUANTIFIER>

	  An example of this kind of QUANTIFIER is:

		    repeat	10  ;

	  The EXPR, the 10 in this example, dictates how many iterations will
	  happen.

	  A QUANTIFIER by itself is never a program.  A QUANTIFIER is ultimately
	  associated with some action, e.g., a STATEMENT, as in the following
	  rule:

		    <QUANTIFIER>	do  <STATEMENT>  end	  ->	    <STATEMENT>

	  As a whole, this STATEMENT denotes the repeated execution of the given
	  STATEMENT appearing between the "do" and "end".  For each iteration
	  caused by the QUANTIFIER, the given STATEMENT is executed once in its
	  entirety.

	  ICL provides many notations that form QUANTIFIERs, including notations
	  for combining given QUANTIFIERs to form new, complex QUANTIFIERs.  It
	  is surprising how clearly and concisely complex quantification can be
	  specified.


20.2.3.1
Quantification Somewhat Like APL

	  In this respect, ICL gains much of the brevity and complex looping
	  supported by the language APL, although ICL's quantification is much
	easer to read and is more flexible.  (See Section 22.3).


20.2.3.2
Quantifiers Within Expressions

	ICL provides many notations to form EXPRs.  An EXPR and QUANTIFIER can
	be combined together with a BOP (e.g., "+") so as to form the
	mathematician's sigma notation for forming sums.  This provides a way
	  to write a sum, or any operation, over a ~set of values as easily as
	  writing it between ~two values.  (See Section 22.1.5).



20.2.4
Declarations

	  Beyond EXPRs, STATEMENTs, and QUANTIFIERs, two major syntactic
	  categories remain.  DECLARATIONs and TYPEXs.	We concentrate on
	  DECLARATIONs now.

	  The part-of-speech DECLARATION provides a way to
	  introduce new variables, new types, and new functions and coercions
	  into the programming universe, such as the variable TWO_PI used
	  earlier.

	  Function declarations provide for a gradual buildup of
	  programs, each of which may call upon others, until an overall goal
	  is reached.  The ability to define and call functions is absolutely
	  essential for building complex computer systems.

	  While numbers are wonderful, higher-level information structures become
	  essential for the clear specification of programs.	For example, the
	  new type ~complex ~number may be desired for a program the models
	  electrical systems.  The single entity ~complex ~number can be used
	  and passed around as easily as individual numbers can be.	 It is much
	  more natural to pass around a single complex number than passing
	  always twice as many entities, passing a complex number's real
	and imaginary parts independently.

	There are many datatypes that are richer than complex numbers; they may
	include many more than two numbers.  Some might include complex numbers
	as part of their data.  Others may use recursion, e.g., to build
	trees and other interesting structures.

	Packaging simpler data to form more complex data does for data what
	functions do for programs.  It supports a gradual buildup of more and
	more complex kinds of data.

	Functions may in fact be declared which take in and produce data of
	these more complex types.  For example, you may have a very flexible
	datatype called PICTURE.  A PICTURE may contain an aritrary number of
	shapes in various colors.  You can write a single function, say PLOT,
	which takes in a PICTURE and causes it to be drawn.  Here, we are
	passing around entire pictures as easily as we might pass around
	individual numbers.



20.2.4.1
Type Expressions (TYPEX)

	To aid in the declaration of new types, there are notations which form
	new types from old types.  These notations belong to the syntactic
	category TYPEX, short for TYPE eXpression.

	A TYPEX can denote any existing type, such as the type REAL.  That is,
	"REAL" is a valid TYPEX, as supported by the rule:

		real	->	<TYPEX>


	Beyond refering to existing types, a new type can be formed from an
	old type.  For example, by enclosing a TYPEX in "{...}", you denote a
	new type which is a ~list or ~set of arbitrarily many elements.
	All of the elements in the list have the same, given type, the
	TYPEX within the "{...}".  For example, the TYPEX:

		{ REAL }

	denotes a ~list (of arbitrary length) whose elements each is a REAL.

	Other notations are provided to form types other than lists, types
	which are called records, variants, processes, and more.

	While TYPEX refers to the construction of new ~types, EXPR refers to
	~instances of those types.  Recall that in a strongly typed language
	like ICL, any value (EXPR) is an instance of some type (TYPEX).  As we
	introduce each new way to form a TYPEX, we will also introduce new
	EXPR notations to go along with them.

	The new EXPR notations will include notations that form new instances
	of the new TYPEX, and that provide for their examination.

	For example, the "{...}" notation for declaring a ~list of REALs has a
	corresponding notation that forms new ~instances (EXPRs) of such
	lists.  The following is an instance of the new list type:

		{ 1 ; 2 ; 3 ; 3.14 ; 4 ; 5 }

	This EXPR notation is supported by the rule:

		{ EXPR ; EXPR ; ... ; EXPR }		->	EXPR

	This EXPR rule was invented exclusively for use in forming instances of
	new list types.  Thus, this EXPR rule will be presented along with the
	TYPEX rule that supports the formation of list types.