Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site frog.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!cybvax0!frog!rfm
From: rfm@frog.UUCP (Bob Mabee, Software)
Newsgroups: net.lang,net.cse
Subject: Re: introductory programming languages
Message-ID: <688@frog.UUCP>
Date: Fri, 7-Mar-86 09:33:07 EST
Article-I.D.: frog.688
Posted: Fri Mar  7 09:33:07 1986
Date-Received: Sun, 9-Mar-86 09:25:56 EST
References: <109@polyob.UUCP> <9378@ritcv.UUCP> <6796@boring.UUCP>
Reply-To: rfm@frog.UUCP (R. F. Mabee)
Followup-To: net.lang
Distribution: net
Organization: Superfrog Heaven [ CRDS, Framingham MA ]
Lines: 118
Xref: watmath net.lang:2204 net.cse:706
Summary: Try PAL

In article <6796@boring.UUCP> steven@mcvax.UUCP (Steven Pemberton) writes:
>In my view, an introductory programming course should teach as much as
>possible about algorithms and programming, and as little as possible about
>the nuts and bolts of programming languages. The programming language used
>should therefore support this as much as possible by allowing algorithms to
>be expressed as closely as possible to their formulation, without the
>language imposing itself too much.

For several years starting around 1966, MIT's second programming course
(FORTRAN was the first, as elsewhere) used a language called PAL, designed
by Jack Wozencraft and Art Evans.  Some of its syntax resembled BCPL, because
its compiler was the first application program written after Martin Richards
brought up the first BCPL compiler.  An earlier version (ancestor?) of PAL
was implemented in LISP, and that influenced its model of data.

PAL had no distinction between statements and expressions, or between
functions and subroutines.  Everything resulted in a value.  ';' was used
only to cause the result of one expression to be discarded before evaluating
the next, and parentheses did the job of BEGIN-END.  The resulting simple
syntax made learning PAL much easier.

PAL used a LISP-like garbage collector, so all data types could be freely
passed around.  Types applied to values rather than to names, so declarations
did not exist (eliminating another batch of arbitrary syntax).  Operators
were not heavily overloaded so wrong-type errors didn't propagate too far.
There were strings of characters with a limited set of operators, and n-tuples
(arrays of arbitrary objects).  n-tuples were not quite like LISP lists
because they carried the implication of easy access to every element but
difficult creation of all-but-the-first.  On the other hand, they were much
easier to grasp for people who had just mastered (?) FORTRAN.

There were assignment and goto expressions, but they were not brought up
until later in the course.  PAL was very useful in a completely applicative
subset, and that helped to teach us to think of the recursive solutions
to a problem before automatically reaching for the iterative version.
Assignment exposed the problem of sharing: two names (or tuple elements)
might or might not share, such that an assignment to one alters the value
of the other.  Function parameters shared with the actual argument, so you
got call-by-reference effects.  I think this is desirable but is also a hump
that stops some students.

PAL had a wealth of name-defining syntactic forms, so that scope/extent could
model all the other languages' rules.  (One of the stated goals of the course
was to give the student a basis for quickly grasping the ideas behind other
languages, so PAL generally had to be a superset.)  It also exposed the LAMBDA
operator directly, so you could create a function with no name (and correct
lexical binding, unlike most LISPs).  In fact, every part of PAL was just a
syntactic sugaring on top of Church's LAMBDA calculus.  The early part of the
course concentrated on that calculus and a blackboard evaluation scheme.  This
groundwork proved invaluable when we were taught that goto could jump to a
label in a function that had already returned -- instead of feeling lost, we
felt we completely understood how a label object could keep a copy of the CSED
state from the time it (the label) was evaluated.

The main idea I would add to PAL before using it for teaching is information
hiding.  PAL had no model for packages, object-oriented programming, or
operator overloading.  Any object that one function can create any other
function can look inside of.

Here is Steve's garbage collection example rewritten in iterative PAL.
I kept his order of definition although it seems harder to follow that way.

def				//  Define accessible_from with global scope.
    accessible_from (graph, root) =
    (	MARK nil;		//  Function call needs arg, doesn't need ().
	SWEEP nil;
	graph
    )
where				//  Define MARK only within accessible_from.
    MARK nil =
    (	let accessible, to_do = make_set (root), make_set (root)
	in
	(   while to_do ^= nil		//  Maybe ^= should be ne ?
		TREAT_NODE (SELECT_NODE nil);
	)			//  This ) defines where where defines. (!)
	where
	    SELECT_NODE nil =
	    (	let nodename = head_set to_do;
		to_do := tail_set to_do;	//  Assumes tail is efficient.
		nodename
	    )
	and			//  Define TREAT with same scope as SELECT.
	    TREAT_NODE nodename =
	    (	let node = lookup (graph, nodename)	//  Find named object.
		in  for i = 1 to Order node do
			if node i %not_in accessible	//  % makes infixed.
			(   add_set (accessible, node i);
			    add_set (to_do, node i)
			)
	    )
    )
and				//  Define SWEEP with same scope as MARK.
    SWEEP nil =
    (	let ktuple = keys graph
	in  for i = 1 to Order ktuple do
		if ktuple i %not_in accessible  //  a %b c means b (a, c).
		then DELETE (graph, ktuple i)
    )

B provides an extremely powerful facility for 'keyed' sets, which simplifies
this example by pruning away many details of implementation.  Otherwise, is it
an advantage in a teaching language?  Or a liability, since it may befuddle?
This is my recursive implementation of those set operations needed above
(using n-tuples linked through first element):

def make_set name = (nil, name)
and add_set (set, name) =
    (set := $set, name)		//  $ unshares, avoids circular list
and head_set set = set 2
and tail_set set = set 1
and not_in (name, set) = Null set ? TRUE
		       | name = head_set set ? FALSE
		       | not_in (name, tail_set set)
def lookup (graph, name) = name = graph 2 ? graph 3
			 | lookup (graph 1, name)
and DELETE (graph, name) = name = graph 2 ? (graph := graph 1)
			 | DELETE (graph 1, name)
and keys graph = Null graph ? nil
	       | keys (graph 1) aug graph 2