







                                 A HOPE TUTORIAL

                         Roger Bailey, Imperial College








                      Functions In Conventional Languages:

  In a language like Pascal, a function is a piece of  'packaged'  program  for
  performing  standard  operations  like  finding  square roots.  To obtain the
  square root of a positive number stored in a variable x, we write:

       sqrt ( x )
  at the point in the program where we want the value, such as:


       writeln ( 1.0 + sqrt ( x ) ) ;

  this is called an application of the function.  The value represented by  "x"
  is  called  the  argument  or  actual parameter.  In this context, the canned
  program computes the square root of "x", "1.0" is added to it and the  result
  is then printed.


  We can also define our own functions specifying how the  result  is  computed
  using ordinary Pascal statements.  Here's a function that returns the greater
  of its two argument values:


       function max ( x, y : INTEGER ) : INTEGER ;
       begin
       if x > y
          then max := x
          else max := y
       end ;


  The identifiers "x" and "y"  are  called  formal  parameters.   They're  used
  inside  the  definition  to  name  the  two  values  that will be supplied as
  arguments when the function is applied.  We can use "max" anywhere we need  a
  value,  just  like  "sqrt".   Here's  how  we  might  use "max" to filter out
  negative values on output:


       writeln ( max ( z, 0 ) ) ;




  Hope Tutorial                                                          Page 1










  A  more  interesting  case  is  when  the  actual  parameter  is  a  function
  application  itself or involves one.  We can use "max" to find the largest of
  three numbers by writing:


       max ( a, max ( b, c ) )


  Combining functions together like this is called composition.  The expression
  is  evaluated  'inside-out'  because  the outer application of "max" can't be
  evaluated until the value  of  its  second  argument  is  known.   The  inner
  application of "max" is therefore evaluated first using the values of "b" and
  "c" and the result is used as the actual parameter of the outer application.


  Another way of combining functions together is to define more  powerful  ones
  using  simpler  ones  as  'building  blocks'.   If  we often need to find the
  largest of three numbers we might define:


       function MaxOf3 ( x, y, z : INTEGER ) : INTEGER ;
       begin
         MaxOf3 := max ( x, max ( y, z ) )
       end ;


  and apply it by writing:


       MaxOf3 ( a, b, c )






                           Programming with functions

  Pascal is called an imperative language because programs written  in  it  are
  recipes for 'doing something'.  If our programs consist only of functions, we
  can concentrate on what the results are  and  ignore  how  they're  computed.
  Forget  that  "sqrt" is a piece of code and think of "sqrt ( x )" as a way of
  writing a value in your program, and you'll get the idea.  You can  think  of
  "MaxOf3"  like  this  as  well  if  you  ignore  the way it works inside.  By
  defining a 'toolkit' of useful functions and  combining  them  together  like
  this,  we  can  build  powerful  programs  that  are  quite short and easy to
  understand.








  Hope Tutorial                                                          Page 2










  In Pascal, functions can only return 'simple' data objects such as numbers or
  characters,  but  real  programs  use big data structures and can't easily be
  written using these functions.  In Hope, functions can  return  any  type  of
  value,  including  data  structures equivalent to Pascal's arrays and records
  and much more.  Programming in Hope has the flavour of simply  'writing  down
  the  answer' by writing an expression that defines it.  This will contain one
  or more function applications to define smaller parts of the  answer.   These
  functions won't usually be built in like "sqrt", so we'll have to define them
  ourselves, but we'll still think of them as definitions of data objects,  and
  not as algorithms for computing them.






                      A simple Hope example -- conditionals

  Let's  see  how  we  can  define  "max"  in  Hope.   Like  Pascal,   it's   a
  strongly-typed  language,  which  means  we  must tell the compiler about the
  types of all objects in our programs  so  it  can  check  that  they're  used
  consistently.   The function definition comes in two parts.  First we declare
  the argument and result types:


       dec max : num # num -> num ;


  "dec" is in bold face because it's a reserved word and you can't use it as  a
  name.   Type  it  in lower case when entering programs.  "max" is the name of
  the function being defined.  Names consist of upper and  lower  case  letters
  (which  are  distinct) and digits, and must start with a letter.  The current
  fashion is to use lower case.  The  layout  isn't  significant  and  you  can
  separate symbols with any number of blanks, tabs and newlines for clarity, as
  in this example.  Symbols need only be separated when they might otherwise be
  confused as one, such as "dec" and "max".


  The next part of the declaration gives the types of the arguments  (read  the
  symbol  ":"  as 'takes a').  Non-negative integers are of the predefined type
  "num" (in lower case).  "#" is read as 'and a'; (or you can use the  reserved
  word  "X").   "->"  is  read as 'yields'.  The semicolon marks the end of the
  declaration, which tells  the  compiler  that  "max"  takes  two  numbers  as
  arguments and returns a single number as its result.


  The result of a function is defined  by  one  or  more  recursion  equations.
  "max" needs only one equation to define it:


       --- max ( x, y ) <=  if x > y then x else y ;




  Hope Tutorial                                                          Page 3










  Read the symbol "---" as 'the value of'.  The expression "max ( x,  y  )"  is
  called  the left-hand side of the equation.  It defines "x" and "y" as formal
  parameters, or local names for the values that  will  be  supplied  when  the
  function  is  applied.  Parameter names are local to the equation, so "x" and
  "y" won't be confused with any other "x" or "y" in the program.   The  symbol
  "<=" is read as 'is defined as'.


  The rest of the equation (called the right-hand  side)  defines  the  result.
  It's  a  conditional  expression.   The  symbols  "if", "then" and "else" are
  reserved words.  Pascal's conditional statement chooses  between  alternative
  actions,  but  Hope's  conditional  expression  chooses  between  alternative
  values, in line with our view that function applications are ways of  writing
  values  rather  than  recipes  for  computing  them.   If  the  value  of the
  expression "x > y" is "true", the value of the whole  conditional  expression
  is the value of "x", otherwise it's the value of "y".  The alternative values
  can be defined by any Hope expressions.


  When the value of a function is defined by  more  than  one  expression  like
  this,  they  are  evaluated in an unspecified order.  On a suitable computer,
  such as the Imperial College ALICE machine, it's even  possible  to  evaluate
  both  expressions  and  the test in parallel and throw away one of the values
  according to the result of the test.






                       Using functions that we've defined

  A Hope program is just a a single expression containing one or more  function
  applications  composed  together.   It's evaluated immediately and the result
  and its type are printed on the screen.  Here's a simple  program  that  uses
  "max", with its output (which is shown in italics):


       max ( 10, 20 ) + max ( 1, max ( 2,3 ) ) ;
       23 : num


  The rules for evaluating the expression are the  same  as  those  of  Pascal:
  function  arguments  are  evaluated  first,  the  functions  are applied, and
  finally other operations are performed in the usual order of priority.










  Hope Tutorial                                                          Page 4










  We can also use existing functions to  define  new  ones.   Here's  the  Hope
  version of "MaxOf3":


       dec MaxOf3 : num # num # num -> num ;
       --- MaxOf3 ( x, y, z ) <= max ( x, max ( y, z ) ) ;






                     A more interesting example - repetition

  Just as Pascal's conditional statement  is  replaced  by  Hope's  conditional
  value,  so  the  repetitive  statement  is  replaced by the repetitive value.
  Here's a Pascal function that multiplies two numbers using repeated addition:


       function mult ( x, y : INTEGER ) : INTEGER ;
       var prod  : INTEGER ;

       begin
         prod := 0 ;
         while y > 0 do
           begin
        prod := prod + x ;
        y := y - 1
           end ;
         mult := prod
       end ;


  It's hard to be sure this function does enough additions (it  took  me  three
  tries  to  get it right) and this seems to be a general problem with loops in
  programs.  A common way of checking imperative programs is to simulate  their
  execution.  If we do this for input values of 2 and 3, we'll find that "prod"
  starts with the value 0 and gets values of 2, 4  and  6  on  successive  loop
  iterations, which suggests the definition is correct.
















  Hope Tutorial                                                          Page 5










  Hope doesn't have any loops, so we must write  all  the  additions  that  the
  Pascal  program  performed  in  a single expression.  It's much easier to see
  that this has the right number of additions:


       dec mult : num # num -> num ;
       --- mult ( x, y ) <= 0 + x + x + ...


  or would be if we knew how many times to write "+ x".   The  hand  simulation
  suggests  we  need  to write it "y" times, which is tricky when we don't know
  the value of "y".  What we do know is that for a  given  value  of  "y",  the
  expressions:


       mult ( x, y )        and       mult ( x, y-1 ) + x


  will have the same number of "+ x" terms if written out in full.  The  second
  one  always  has two terms, whatever the value of "y", so we'll use it as the
  definition of "mult":


       --- mult ( x, y ) <= mult ( x, y-1 ) + x ;


  On the face of it we've written something ridiculous,  because  it  means  we
  must apply "mult" to find the value of "mult".  Remember however that this is
  really shorthand for "0" followed by "y" occurrences of "+ x".  When  "y"  is
  zero, the result of "mult" is also zero because there are no "+ x" terms.  In
  this case "mult" isn't defined in terms of itself, so if  we  add  a  special
  test for it, the definition terminates.  A usable definition of "mult" is:


       --- mult ( x, y ) <= if y = 0 then 0 else mult ( x, y-1 ) + x ;


  Functions that are defined using themselves like this are  called  recursive.
  Every Pascal program using a loop can be expressed as a recursive function in
  Hope.  All recursive definitions need one case (called the base  case)  where
  the  function  isn't  defined in terms of itself, just as Pascal loops need a
  terminating condition.













  Hope Tutorial                                                          Page 6










                         Another way of using functions

  Hope allows us to use a function with two arguments like "mult" as  an  infix
  operator.   We must assign it a priority and use it as an operator everywhere
  including the equations that definine it.  The definition of "mult" when used
  as an infix operator looks like this:


       infix mult : 8 ;
       dec mult : num # num -> num ;
       --- x mult y <= if y = 0 then 0 else x mult ( y - 1 ) + x ;


  A bigger number in the infix declaration means a higher priority.  The second
  argument of "mult" is parenthesised because its priority of 8 is greater than
  the built-in subtraction operation.  Most of Hope's  standard  functions  are
  supplied as infix operators.






                               Other kinds of data


  Hope provides two other primitive data types.  A "truval"  (truth  value)  is
  equivalent  to  a  Pascal  Boolean  and has values "true" and "false".  We've
  already seen the expression "x >  y"  defining  a  truth  value.   ">"  is  a
  standard  function  whose  type  is  "num # num -> truval".  We can use truth
  values in conditional expressions and combine them together with the standard
  functions "and", "or" and "not".


  Single characters are of type "char", with values "'a'",  "'b'"  and  so  on.
  Characters  are  most  useful  as  components  of  data  structures  such  as
  character-strings.


















  Hope Tutorial                                                          Page 7










                                 Data structures

  Practical programs need data structures  and  Hope  has  two  standard  kinds
  already  built  in.  The simplest kind corresponds to a Pascal record. We can
  bind a fixed number of objects of any type together into a structure called a
  tuple, for example:


       ( 2, 3 )       or        ( 'a', true )


  are tuples of type "num # num" and "char  #  truval"  respectively.   We  use
  tuples  when  we  want  a function to define more than one value.  Here's one
  that defines the time of day given the number of seconds since midnight:


       dec time24 : num -> num # num # num ;
       --- time24 ( s ) <= ( s div 3600,
                        s mod 3600 div 60,
                        s mod 3600 mod 60  ) ;


  "div" is the built-in integer division function and "mod" gives the remainder
  after  integer  division.   If  we  type  an  application  of "time24" at the
  terminal, the result tuple and its type will be printed on the screen in  the
  usual way:


       time24 ( 45756 ) ;
       ( 12,42,36 ) : ( num # num # num )

























  Hope Tutorial                                                          Page 8










  The second standard data type,  called  a  list,  corresponds  roughly  to  a
  one-dimensional  array  in  Pascal.   It  can  contain  any number of objects
  (including none at all) but they must all be the same  type.   We  can  write
  expressions in our programs that represent lists, such as:


       [ 1, 2, 3 ]


  which is of type "list ( num  )".   There  are  two  standard  functions  for
  defining  lists.   The infix operator "::" (read as 'cons') defines a list in
  terms of a single object and list containing the same type of object, so


       10 :: [ 20, 30, 40 ]


  defines the list:


       [ 10, 20, 30, 40 ]


  Don't think of "::" as adding "10" to the front of "[  20,  30,  40  ]".   It
  really  definines  a  new  list  "[  10,  20, 30, 40 ]" in terms of two other
  objects without changing their meaning, rather in the same way that "1  +  3"
  defines a new value of "4" without changing the meaning of "1" or "3".


  The other standard list function is "nil",  which  defines  a  list  with  no
  elements  in  it.  We can represent every list by an expression consisting of
  applications of "::" and "nil".  When we write an expression like:


       [ a + 1, b - 2, c * d ]


  it's considered to be a shorthand way of writing:


       a + 1 :: ( b - 2 :: ( c * d :: nil ) )


  There's also a shorthand way of writing lists of characters.   The  following
  three expressions are all equivalent:


       "cat"        [ 'c', 'a', 't' ]        'c' :: ( 'a' :: ( 't' :: nil ) )







  Hope Tutorial                                                          Page 9










  When the result of a Hope program is a list, it's always printed out  in  the
  concise  bracketed  notation;  if  it's a list of characters, it's printed in
  quotes.


  Every data type in Hope is defined by a set of primitive functions like  "::"
  and  "nil".   They're  called  constructor  functions,  and aren't defined by
  recursion equations.  When we defined a  tuple,  we  were  actually  using  a
  standard  constructor  called  "," (read as 'comma').  Later on we'll see how
  constructors are defined for other types of data.





                           Functions that define lists


  If we wanted to write a Pascal program to print the first n  natural  numbers
  in  descending order we'd probably write a loop that printed one value out on
  each iteration, such as:


       for i := n downto 1 do write ( i ) ;


  In Hope we write one expression that defines all the values at  once,  rather
  like we did for "mult":


       dec nats : num -> list ( num ) ;
       --- nats ( n ) <= if n = 0 then nil else n :: nats ( n-1 ) ;


  "nil" is useful for writing the  base  case  of  a  recursive  function  that
  defines a list.  If we try the function at the terminal by typing:


       nats ( 10 ) ;
       [ 10,9,8,7,6,5,4,3,2,1 ] : list ( num )


  we can see that the numbers are in descending order because that's the way we
  arranged  them  in the list, and not because they were defined in that order.
  The values in the expression defining the list are  treated  as  though  they
  were  all generated at the same time.  On the ALICE machine they actually are
  generated at the same time.








  Hope Tutorial                                                         Page 10










  To get the results of a Hope program in the right order, we must put them  in
  the  right  place  in  the  final data structure.  If we want the list of the
  numbers "n" through "1" in the opposite order we can't write  the  definition
  as:


       ...  else nats ( n-1 ) :: n ;


  because the argument types for "::" are the wrong way round.  We need to  use
  a  another  built-in  operation "<>" (read as 'append') that concatenates two
  lists.  The definition will then look like this:


       --- nats ( n ) <= if n = 0 then nil else nats ( n-1 ) <> [ n ] ;


  We put "n" in brackets to make it into  a  (single-item)  list  because  "<>"
  expects  both  its arguments to be lists.  We could also have written "( n ::
  nil )" instead of "[ n ]".






                          Data structures as parameters


  Suppose we have a list of integers and we want to write a function to add  up
  all its elements.  The declaration will look like this:


       dec sumlist : list ( num ) -> num ;


  We need to refer to the individual elements of the actual  parameter  in  the
  equations  defining  "sumlist".  We do this using an equation whose left-hand
  side looks like this:


       --- sumlist ( x :: y ) ...













  Hope Tutorial                                                         Page 11










  This is an expression involving  list  constructors  and  corresponds  to  an
  actual  parameter that's a list.  "x" and "y" are formal parameters, but they
  now name individual parts of the actual parameter value.  In  an  application
  of "sumlist" like:


       sumlist ( [ 1, 2, 3 ] )


  the actual parameter will be 'dismantled' so that "x" names the value "1" and
  "y" names the value "[ 2, 3 ]".  The complete equation will be:


       --- sumlist ( x :: y ) <= x + sumlist ( y ) ;


  Notice there's no base case test.  As we might expect, it's the  empty  list,
  but  we  can't test for it directly in the equation because there's no formal
  parameter that  refers  to  the  whole  list.   In  fact,  if  we  write  the
  application:


       sumlist ( nil )


  we'll get an error message because we  can't  dismantle  "nil"  to  find  the
  values  of  "x"  and  "y".  We must cover this case separately using a second
  recursion equation:


       --- sumlist ( nil ) <= 0 ;


  The two equations can be given in either order.  When "sumlist"  is  applied,
  the  actual  parameter is examined to see which constructor function was used
  to define it.  If the  actual  parameter  is  a  non-empty  list,  the  first
  equation  is  used,  because  non-empty  lists  are  defined  using  the "::"
  constructor.  The first number in the list gets named "x" and  the  remaining
  list  "y".  If the actual parameter is the empty list, the second equation is
  be used because empty lists are defined using the constructor "nil".















  Hope Tutorial                                                         Page 12










                                Pattern-matching

  An expression composed of constructors appearing on the left-hand side  of  a
  recursion  equation  is  called  a  pattern.   Selecting  the right recursion
  equation and dismantling the actual parameter to name  its  parts  is  called
  pattern-matching.   When  you  write  a  function,  you must give a recursion
  equation for each possible constructor defining the argument type.


  Sometimes we don't need to dismantle the actual parameter, and we can  use  a
  formal  parameter  in the pattern that matches the whole object, irrespective
  of what constructors were used to define it.  As an example, let's see how we
  could  define  our  own  function  to concatenate two lists like the built-in
  operation "<>":


       infix cat : 4 ;
       dec cat : list( num ) # list( num ) -> list ( num ) ;
       --- ( h :: t ) cat l <= h :: ( t cat l ) ;
       --- nil cat l <= l ;


  The first list parameter is matched by the pattern "( h :: t )" so  that  its
  first  item  (the 'head") and the remaining list (the 'tail') can be referred
  to separately on the right-hand side.  The second recursion  equation  covers
  the  case when the first list is empty.  The second list parameter is matched
  by the pattern "l" whether it's empty or not.


  As well as writing enough recursion equations to satisfy  all  the  parameter
  constructors,  we  must  also be careful not to write sets of equations where
  more than one pattern might match the actual parameters, because  that  would
  be ambiguous.


  We can write patterns to match arguments that are  tuples  in  the  same  way
  using  the tuple constructor ",".  When we wrote "mult ( x, y )" you probably
  thought the parentheses and the comma were something to do with the  function
  application.   In fact, we were constructing a tuple and the parentheses were
  only needed because "," has a low priority.  Hope  treats  all  functions  as
  having  only  one  argument.  This can be a tuple when you want the effect of
  several arguments.  Without parentheses,


       mult x, y


  would be interpreted as:


       ( mult ( x ), y )




  Hope Tutorial                                                         Page 13










  A recursion equation with the left-hand side:


       --- mult ( x, y ) <= ...


  is just a pattern-match on a tuple.  The first item in the tuple  gets  named
  "x" and the second one "y".


  We can also use pattern-matching on "num" parameters.  These are  defined  by
  two  constructors called "succ" and "0".  "succ" defines a number in terms of
  the next lower one.  "0" has no arguments and defines the value zero.  Surely
  "0"  is  a  value,  not  a  function? Well, we're already used to thinking of
  function applications as  another  way  of  writing  values,  so  it's  quite
  consistent  to  think  of "0" as a function application.  Here's a version of
  "mult" that uses pattern-matching to identify the base case:


       infix mult : 8 ;
       dec mult : num # num -> num ;
       --- x mult 0          <= 0 ;
       --- x mult succ ( y ) <= ( x mult y ) + x ;


  We can read "succ ( y )" as 'the successor of some  number  that  we'll  call
  "y"'.  Instead of naming the actual parameter "y" like we did in the original
  version of "mult", we're naming its predecessor.



























  Hope Tutorial                                                         Page 14










                             Simplifying expressions

  In Pascal programs we can simplify complex  expressions  by  removing  common
  sub-expressions and evaluating them separately.  Instead of:


       writeln ( ( x + y ) * ( x + y ) ) ;


  we would probably write:


       z := x + y ; writeln ( z * z ) ;


  which  is  clearer  and  more  efficient.   Hope  programs  consist  only  of
  expressions  and  it's  even  more important to simplify them.  We do this by
  using a qualified expression:


       let z == x + y in z * z ;


  This looks like an assignment, but it isn't.  "==" is read as 'is defined as'
  and "z" is local to the expression following the "in".  If we write something
  like:


       let z == z + 1 in z * z ;


  we're actually introducing a new variable "z" to use in the sub-expression "z
  * z".  It hides the original one in the sub-expression "z + 1".


  There's a second form of qualified expression for  people  who  like  to  use
  variables first and define their meanings later.  It looks like this:


       z * z where z == x + y ;


  The result of the qualified expression is the same whether we define it using
  let  or where.  "x + y" is evaluated first, and its value is used in the main
  expression.










  Hope Tutorial                                                         Page 15










  The qualifying expression will often be a function application that defines a
  data  structure.   If  we  want  to  name  part of the structure we can use a
  pattern on the left-hand side of the "==" symbol:


       dec time12 : num -> num # num ;
       --- time12 ( s ) <= ( if h > 12 then h-12 else h, m ) where
                      ( h, m, s ) == time24 ( s ) ;


  We'll use this construction most often when we write recursive functions that
  define  tuples.   Here's a typical example.  Suppose we want to form a string
  of words from a sentence.  For simplicity a word is taken to be any  sequence
  of  characters,  and  words  are  separated  in the sentence by any number of
  blanks.  The sentence and a single word will be of type "list ( char  )"  and
  the final sequence of words a "list ( list ( char ) )".


  It's fairly straightforward to obtain the first word.  Here's a function that
  does it:


       dec firsttry : list ( char ) -> list ( char ) ;
       --- firsttry ( nil )    <= nil ;
       --- firsttry ( c :: s ) <= if c = ' '
                               then nil
                               else c :: firsttry ( s ) ;


  One of the nice features of Hope is that we can type in  and  print  out  any
  kind  of  value,  so  it's  easy to check out the individual functions of our
  program separately.  If we test "firsttry" we'll see:


       firsttry ( "You may hunt it with forks and Hope" ) ;
       "You" : list ( char )


  But there's a problem here because we're  going  to  need  the  rest  of  the
  sentence if we're to find the remaining words.  We must arrange that that the
  function returns the remaining list as well as the first word.  This is where
  tuples come in:


       dec firstword : list ( char ) -> list ( char ) # list ( char ) ;
       --- firstword ( nil )    <= ( nil, nil ) ;
       --- firstword ( c :: s ) <= if c = ' '
                                then ( nil, s )
                                else ( ( c :: w, r ) where
                                       ( w, r ) == firstword ( s ) ) ;





  Hope Tutorial                                                         Page 16










  The  qualified  expression  is  parenthesised  so  it  only  applies  to  the
  expression after the else, otherwise we'll evaluate "firstword" recursivly as
  long as the sentence is non-empty, even if it  starts  with  a  blank.   This
  version of the function produces:


       firstword ( "Hope springs eternal ..." ) ;
       ( "Hope","springs eternal ..." ) : ( list ( char ) # list ( char ) )


  We can use this to define a function to split the sentence into a list of its
  individual words:


       dec wordlist : list ( char ) -> list ( list ( char ) ) ;
       --- wordlist ( nil )    <= nil ;
       --- wordlist ( c :: s ) <= if c = ' '
                               then wordlist( s )
                               else ( w :: wordlist ( r ) where
                                    ( w, r ) == firstword ( c :: s ) ) ;


  which we can test by typing an application at the terminal:


       wordlist ( "  While there's life there's Hope  " ) ;
       [ "While","there's","life","there's","Hope" ] : list ( list ( char ) )






                                     Review

  So far we've concentrated on features of Hope that have something  in  common
  with  traditional  languages  such  as  Pascal,  but  without  many  of their
  limitations, such as fixed-size data structures.  We've also been  introduced
  to  the  functional style of programming where programs are no longer recipes
  for action, but just definitions of data objects.


  Now we'll introduce features of Hope that lift it onto a much higher level of
  expressive  power,  and  let  us  write  programs that are not only extremely
  powerful and concise, but that can be checked for correctness at compile-time
  and mechanically transformed into more efficient versions.









  Hope Tutorial                                                         Page 17










                         Making functions more powerful

  The Hope compiler can spot many common kinds of error by checking  the  types
  of all objects in expressions.  This is harder than checking at run-time, but
  more efficient and  saves  the  embarrassment  of  discovering  an  error  at
  run-time  in  a  rarely-executed  branch of the air traffic control system we
  just wrote.


  However, strict type-checking can be a nuisance if we want  to  perform  some
  operation  that doesn't depend on the type of the data.  Try writing a Pascal
  procedure to reverse an array of either 10  integers  or  10  characters  and
  you'll see what I mean.


  Hope avoids this kind of restriction by allowing a  function  to  operate  on
  more  than  one type of object.  We've already used the standard constructors
  "::" and "nil" to define a "list ( num )", a "list ( char )" and  a  "list  (
  list  (  char  ) )".  The standard equality function "=" will compare any two
  objects  of  the  same  type.   Functions  with  this  property  are   called
  polymorphic.  Pascal's built-in functions "abs" and "sqr" and operations like
  ">" and "=" are polymorphic in a primitive kind of way.


  We can define our own polymorphic functions in Hope.  The function  "cat"  we
  defined  above will concatenate lists of numbers, but we can use it for lists
  containing any type of object.  To  do  this  we  first  declare  a  kind  of
  'universal  type'  called a type variable.  We use this in the declaration of
  "cat" where it stands for any actual type:


       typevar alpha ;
       infix cat : 8 ;
       dec cat : list ( alpha ) # list ( alpha ) -> list ( alpha ) ;


  This says that "cat" has two parameters that are lists and  defines  a  list,
  but  it  doesn't  say  what  kind of object is in the list.  However, "alpha"
  always stands for the same type throughout a given declaration,  so  all  the
  lists must contain the same type of object.  The expressions:


       [ 1,2,3 ]  cat  [ 4,5,6 ]         and         "123"  cat  "456"


  are correctly-typed applications of "cat" and define a "list ( num )"  and  a
  "list ( char )" respectively, while the expression:


       [ 1,2,3 ]  cat  "456"





  Hope Tutorial                                                         Page 18










  isn't because "alpha" can't be  interpreted  as  two  different  types.   The
  interpretation  of  a  type variable is local to a declaration so it can have
  different interpretations in other declarations without confusion.


  Of course it only makes sense for a function to be polymorphic as long as the
  equations defining it don't make any assumptions about types.  In the case of
  "cat" the  definition  uses  only  "::"  and  "nil",  which  are  polymorphic
  themselves.  However, a function like "sumlist" uses "+" and can only be used
  with lists of numbers as parameters.






                          Defining your own data types

  Tuples and lists are quite powerful, but for more sophisticated applications,
  we'll need to define our own types.  User-defined types make programs clearer
  and help the type-checker to help the programmer.  We introduce  a  new  data
  type in a data declaration:


       data vague == yes ++ no ++ maybe ;


  "data" is a reserved word and "vague" is the name of the new type.   "=="  is
  read  as  'is  defined as' and "++" is read as 'or'.  "yes", "no" and "maybe"
  are the names for the constructor functions of the  new  type.   We  can  now
  write function definitions that use these constructors in patterns:


       dec evade : vague -> vague ;
       --- evade ( yes )   <= maybe ;
       --- evade ( maybe ) <= no ;


  The constructors can be parameterised with any type of object, including  the
  type that's being defined.  We can define types like lists, whose objects are
  of unlimited size using this kind of recursive definition.   As  an  example,
  here's a user-defined binary tree that can contain numbers as its leaves:


       data tree == empty ++ tip ( num ) ++ node ( tree # tree ) ;










  Hope Tutorial                                                         Page 19










  There are three constructors.  "empty" has no parameters and defines  a  tree
  with  nothing  in  it.   "tip"  defines  a tree in terms of a single num, and
  "node" defines a tree in terms of two other trees.  Here's a typical tree:


                                        .
                                       / \
                                      /   \
                                  ___/     \___
                         ________/             \________
                        /       /               \       \
                       /       /\               /\       \
                      1       /  \             /  \       \
                             /    \           /    \       5
                            2      3         .      4


  Here's an example of a function that manipulates trees.  It returns  the  sum
  of all the numbers contained in one:


       dec sumtree : tree -> num ;
       --- sumtree ( empty )         <= 0 ;
       --- sumtree ( tip ( n ) )     <= n ;
       --- sumtree ( node ( l, r ) ) <= sumtree ( l ) + sumtree ( r ) ;


  Unfortunately there's no shorthand for writing tree constants like  there  is
  for  list  constants,  so  we've  got  to  write  them out the long way using
  constructors.  If we want to use "sumtree" to add up all the numbers  in  the
  example tree above, we must type in the expression:


       sumtree ( node ( node ( tip ( 1 ),
                          node ( tip ( 2 ),
                                 tip ( 3 ) ) ),
                   node ( node ( empty,
                                 tip ( 4 ) ),
                          tip ( 5 ) ) ) ) ;


  This isn't really a drawback, because programs that manipulate  complex  data
  structures  like  trees  will  generally  define  them using other functions.
  However, it's very useful to be able  to  type  any  kind  of  constant  data
  structure at the terminal when we're checking out an individual function like
  "sumtree".  When we want to test a Pascal program piecemeal, we usually  have
  to write elaborate test harnesses or stubs to generate test data.








  Hope Tutorial                                                         Page 20










                            Making data more abstract

  The identifier "list" isn't really a Hope data  type.   It's  called  a  type
  constructor  and  must  be  parameterised  with  an  actual  type  before  it
  represents one.  We did this every time we declared a "list (  num  )"  or  a
  "list  (  char  )".  The parameter can also be a user-defined type, as with a
  "list ( tree )" or even a type variable as in "list ( alpha )", which defines
  a  polymorphic  data  type.   Constructing  new  data  types  like  this is a
  compile-time operation  by  the  way,  and  you  shouldn't  confuse  it  with
  constructing new data values, which is a run-time operation.


  You can define your own polymorphic data types.   Here's  a  version  of  the
  binary tree we defined earlier that can have any type of value in its leaves:


       data tree ( alpha ) == empty ++
                         tip ( alpha ) ++
                         node ( tree ( alpha ) # tree ( alpha ) ) ;


  Once again, "alpha" is taken to be the same type throughout one instance of a
  tree.  If it's a number, then all references to "tree ( alpha )" are taken as
  references to "tree ( num )".


  We can define polymorphic functions that operate on trees containing any type
  of  object, because tree constructors are now polymorphic.  Here's a function
  to 'flatten' a binary tree into a list of the same type of object:


       dec flatten : tree ( alpha ) -> list ( alpha ) ;
       --- flatten ( empty )         <= nil ;
       --- flatten ( tip ( x ) )     <= x :: nil ;
       --- flatten ( node ( x, y ) ) <= flatten ( x ) <> flatten ( y ) ;




















  Hope Tutorial                                                         Page 21










  We can demonstrate it on various kinds of tree:


       flatten( node ( tip ( 1 ), node ( tip ( 2 ), tip ( 3 ) ) ) ) ;
       [ 1, 2, 3 ] : list ( num )


       flatten( node ( tip ( "one" ),
                  node ( tip ( "two" ),
                         tip ( "three" ) ) ) ) ;
       [ "one","two","three" ] : list ( list ( char ) )


       flatten( node ( tip ( tip ( 'a' ) ),
                  node ( tip ( empty ),
                         tip ( node ( tip ( 'c' ),
                                      empty ) ) ) ) ) ;
       [ tip ( 'a' ),empty,node ( tip ( 'c' ), empty) ] : list ( tree ( char ) )


  Notice how the type-checker may need to go through  several  levels  of  data
  types to deduce the type of the result.

































  Hope Tutorial                                                         Page 22










                           Even more concise programs

  The importance of polymorphic types and functions is that they let  us  write
  shorter,  clearer programs.  It's similar to the way Pascal procedures let us
  use the same code  to  operate  on  different  data  values,  but  much  more
  powerful.   We  can write a single Hope function to reverse a list of numbers
  or characters, where we'd need to write two identical Pascal  subroutines  to
  reverse an array of integers and an array of characters.

  We can use polymorphic functions  whenever  we're  concerned  only  with  the
  arrangement  of  the  objects  in a data structure and not with their values.
  Sometimes, we'll want to apply some function to the primitive data  items  in
  the  structure.   Here's  a  function that uses a second function "square" to
  define a "list (num)" whose elements are the squares of another "list (num)":


       dec square : num -> num ;
       --- square ( n ) <= n * n ;


       dec squarelist : list ( num ) -> list ( num ) ;
       --- squarelist ( nil )    <= nil ;
       --- squarelist ( n :: l ) <= square ( n ) :: squarelist ( l ) ;


  Every time we write a function to process every  element  of  a  list,  we'll
  write  something  almost  identical  to  "squarelist".   Here's a function to
  define a list of factorials:


       dec fact : num -> num ;
       --- fact ( 0 )          <= 1 ;
       --- fact ( succ ( n ) ) <= succ ( n ) * fact ( n ) ;


       dec factlist : list ( num ) -> list ( num ) ;
       --- factlist ( nil )    <= nil ;
       --- factlist ( n :: l ) <= fact ( n ) :: factlist ( l ) ;


  "factlist" has exactly the same 'shape'  as  "squarelist",  it  just  applies
  "fact"  instead of "square" and then applies itself recursively.  Values that
  differ between applications are usually supplied as actual  parameters.  Hope
  treats  functions  as  data objects, so we can do this in a perfectly natural
  way.  A function that can take another function as  an  actual  parameter  is
  called  a higher-order function.  When we declare it we must give the type of
  formal parameter standing for the function in the usual way.  The declaration
  of "fact" tells us that it's:

       num -> num





  Hope Tutorial                                                         Page 23










  Read this as 'a function mapping numbers to numbers'.  Now let's see  how  we
  can  use  this  idea to write "factlist" and "squarelist" as a single higher-
  order function.  The new function needs two parameters,  the  original  list,
  and the function that's applied inside it.  Its declaration will be:


       dec alllist : list ( num ) # ( num -> num ) -> list ( num ) ;


  The 'shape' of "alllist" will be the same as "factlist" and "squarelist", but
  the  function  we  apply  to  each  element  of  the  list will be the formal
  parameter:


       --- alllist ( nil, f )    <= nil ;
       --- alllist ( n :: l, f ) <= f ( n ) :: alllist ( l, f ) ;


  We use "alllist" like this:


       alllist ( [ 2,4,6 ], square ) ;
       [ 4,16,36 ] : list ( num )


       alllist ( [ 2,4,6 ], fact ) ;
       [ 2,24,720 ] : list ( num )


  Notice that there's  no  argument  list  after  "square"  or  "fact"  in  the
  application  of  "alllist",  so  this  construction  won't  be  confused with
  functional composition.  "fact( 3 )" represents a function  application,  but
  "fact" by itself represents the unevaluated function.


  Higher-order functions can also be polymorphic.  We  can  use  this  idea  to
  write  a  more  powerful  version  of  "alllist" that will apply an arbitrary
  function to every element of a list  of  objects  of  arbitrary  type.   This
  version of the function is usually known as "map":


       typevar alpha, beta ;
       dec map : list ( alpha ) # ( alpha -> beta ) -> list ( beta ) ;
       --- map ( nil, f ) <= nil ;
       --- map ( n :: l, f ) <= f ( n ) :: map ( l, f ) ;


  The definition now uses two type variables  "alpha"  and  "beta".   Each  one
  represents the same actual type throughout one instance of "map", but the two
  types can be different.  This means we can use any function that maps  alphas
  to betas to generate a list of betas from any list of alphas.




  Hope Tutorial                                                         Page 24










  The actual types aren't restricted to scalars, which makes "map" rather  more
  powerful  than we might realise at first sight.  Suppose we've got a suitably
  polymorphic function that finds the length of a list:


       typevar gamma ;
       dec length : list ( gamma ) -> num ;
       --- length ( nil )    <= 0 ;
       --- length ( n :: l ) <= 1 + length ( l ) ;


       length ( [ 2,4,6,8 ] ) + length ( "cat" ) ;
       7 : num


  We can use "map" to apply "length" to  every  element  of  a  list  of  words
  defined by "wordlist":


       map ( wordlist ( "The form remains, the function never dies" ), length )
       [ 3,4,8,3,8,5,4 ] : list ( num ) ;


  In this example "alpha" is taken to be a "list ( char )" and "beta" to  be  a
  num, so the type of the function must be "( list ( char ) -> num )". "length"
  fits the bill if "gamma" is taken to be a character.





























  Hope Tutorial                                                         Page 25










                          Common patterns of recursion

  "map" is powerful because it sums up a pattern of  recursion  that  turns  up
  frequently  in  Hope  programs.   We  can  see  another common pattern in the
  function "length" used above.  Here's another example of the same pattern:


       dec sum : list ( num ) -> num ;
       --- sum ( nil )    <= 0 ;
       --- sum ( n :: l ) <= n + sum ( l ) ;


  The underlying pattern consists of processing each element in  the  list  and
  accumulating  a  single  value that forms the result.  In "sum", each element
  contributes its value to the final result.  In "length" the  contribution  is
  always  "1" irrespective of the type or value of the element, but the pattern
  is identical.  Functions that display this pattern are of type:


       ( list ( alpha ) -> beta )


  In the function definition, the equation for a non-empty list parameter  will
  specify  an  operation  whose result is a "beta".  This is "+" in the case of
  "length" and "sum".  One argument of the operation will be a list element and
  the  other  will be defined by a recursive call, so the type of the operation
  needs to be:


       ( alpha # beta -> beta )


  This operation differs between applications, so it  will  be  supplied  as  a
  parameter.   Finally  we  need a parameter of type "beta" to specify the base
  case result.  The final version of the function is usually known as "reduce".
  In  the  following  definition,  the  symbol  "!" introduces a comment, which
  finishes with another "!" or with a newline:


       dec reduce :   list ( alpha ) #            ! the input list          !
                      ( alpha # beta -> beta ) #  ! the reduction operation !
                      beta                        ! the base case result    !
                  ->  beta ;                      ! the result type         !
       --- reduce ( nil, f, b )    <= b ;
       --- reduce ( n :: l, f, b ) <= f ( n, reduce ( l, f, b ) ) ;










  Hope Tutorial                                                         Page 26










  To use "reduce" as a replacement for "sum" we'll need to supply the  standard
  function "+" as an actual parameter.  We can do this if we prefix it with the
  symbol nonop to tell the compiler we  don't  want  to  use  it  as  an  infix
  operator:


       reduce ( [ 1,2,3 ], nonop +, 0 ) ;
       6 : num


  When we use "reduce" as a replacement for "length", we're not  interested  in
  the  first  argument  of  the  reduction  operation because we always add "1"
  whatever the list element is.  This function ignores its first argument:


       dec addone : alpha # num -> num ;
       --- addone ( _ , n ) <= n + 1 ;


  We use "_" to represent any argument we don't want to refer to.


       reduce ( "a map they could all understand", addone, 0 ) ;
       31 : num


  Like "map", "reduce" is much more powerful than it first appears because  the
  reduction  function needn't define a scalar.  Here's a candidate that inserts
  an object into an ordered list of the same kind of object:


       dec insert : alpha # list ( alpha ) -> list ( alpha ) ;
       --- insert ( i, nil )    <= i :: nil ;
       --- insert ( i, h :: t ) <= if i < h
                                then i :: ( h :: t )
                                else h :: insert ( i, t ) ;



















  Hope Tutorial                                                         Page 27










  Actually this isn't strictly polymorphic as its declaration suggests, because
  it  uses  the  built-in  function "<", which is only defined over numbers and
  characters, but it shows the kind of thing we can do.   When  we  use  it  to
  reduce a list of characters:


       reduce ( "All sorts and conditions of men", insert, nil ) ;
       "     Aacddefiillmnnnnoooorssstt" : list ( char )


  we can see that it actually sorts them.  The sorting method (insertion  sort)
  isn't  very  efficient,  but  the  example  shows  something  of the power of
  higher-order functions and of "reduce" in particular.  It's even possible  to
  use  "reduce"  to get the effect of "map", but that's left as an exercise for
  the reader as they say.


  Of course "map" and "reduce" only work on "list ( alpha )" and we'll need  to
  provide  different  versions  for our own structured data types.  This is the
  preferred style of  Hope  programming,  because  it  makes  programs  largely
  independent  of  the  'shape'  of  the  data  structures they use.  Here's an
  alternative kind of binary tree that holds data at its nodes rather than  its
  tips, and a reduce function for it:


       data tree ( alpha ) == empty ++
                         node ( tree ( alpha ) # alpha # tree ( alpha ) ) ;

       dec redtree : tree ( alpha ) #
                ( alpha # beta -> beta ) #
                beta -> beta ;
       --- redtree ( empty, f, b )            <= b ;
       --- redtree ( node ( l, v, r ), f, b ) <=
                redtree ( l, f, f ( v, redtree ( r, f, b ) ) ) ;


  We can use this kind of tree to define a more  efficient  sort.   An  ordered
  binary  tree  has  the  property  that  all  the  objects in its left subtree
  logically precede the node object and all those  in  its  right  subtree  are
  equal  to  the  node object or logically succeed it.  We can build an ordered
  tree if we have a function to insert  new  objects  into  an  already-ordered
  tree, such as:


       dec instree : alpha # tree ( alpha ) -> tree ( alpha ) ;
       --- instree ( i, empty ) <= node ( empty, i, empty ) ;
       --- instree ( i, node ( l, v, r ) ) <=
                if i < v
                 then node ( instree ( i, l ), v, r )
                 else node ( l, v, instree ( i, r ) ) ;





  Hope Tutorial                                                         Page 28










  We can sort a list by converting its elements  into  an  ordered  tree  using
  "instree",  then  flattening the tree back into a list.  This is very easy to
  specify using the two kinds of reduction we've defined:


       dec sort : list ( alpha ) -> list ( alpha ) ;
       --- sort ( l ) <= redtree( reduce ( l, instree, empty ), nonop ::, nil )


       sort ( "Mad dogs and Englishmen" ) ;
       "   EMaadddegghilmnnnoss" : list ( char )






                               Anonymous functions

  When we used "map" and "reduce", we had to define extra functions like "fact"
  and  "square" to pass in as paramteters.  This is a nuisance if we don't need
  them anywhere else in the program and especially  if  they're  trivial,  like
  "sum"  or  "addone".   For  on-the-spot use in cases like this, we can use an
  anonymous function called a lambda-expression.   Here's  a  lambda-expression
  corresponding to "sum":


       lambda ( x, y ) => x + y


  The symbol "lambda" introduces the function and  "x" and "y" are  its  formal
  parameters.   The  expression  "x  + y" is the function definition.  The part
  after "lambda" is just a recursion equation without the "---" and  with  "=>"
  instead  of  "<=".   Here's  another  lambda-expression  used  as  the actual
  parameter of "reduce":


       reduce ( [ "toe","tac","tic" ], lambda ( a, b ) => b <> a, nil ) ;
       "tictactoe" : list ( char )


  There can be more than one recursion  equation  in  the  lambda-  expression.
  They're  separated  from each other by the symbol "|" and pattern-matching is
  used  to  select  the  appropriate  one.   Here's  an   example   that   uses
  pattern-matching  in  a  lambda-expression to avoid division by zero when the
  function it defines is executed:


       map ( [ 1,0,2,0,3 ], lambda ( 0 )          => 0
                            | ( succ ( n ) ) => 100 div succ ( n ) ) ;
       [ 100,0,50,0,33 ] : list ( num )




  Hope Tutorial                                                         Page 29










                       Functions that create new functions

  As we've seen, Hope functions possess 'full rights'  and  can  be  passed  as
  actual  parameters  like any data object.  It'll be no surprise to learn that
  we can return a function as the result of another function.  The  result  can
  be  a named function or an anonymous function defined by a lambda-expression.
  Here's a simple example:


       dec makestep : num -> ( num -> num ) ;
       --- makestep ( i ) <= lambda ( x ) => i + x ;


       makestep ( 3 ) ;
       lambda ( x ) => 3 + x : num -> num


  As we can see from trying "makestep", its result  is  an  anonymous  function
  that adds a fixed quantity to its single argument.  The size of the increment
  was specified as an actual parameter to "makestep" when the new function  was
  created,  and  has  become  'bound  in' to its definition.  If we try the new
  function, we'll see that it really does add "3" to its actual parameter:


       makestep ( 3 ) ( 10 ) ;
       13 : num


  There are two applications here.  First we apply "makestep" to "3", then  the
  resulting  anonymous function is applied to "10".  Finally, here's a function
  that has functions as both actual parameter and result:


       dec twice : ( alpha -> alpha ) -> ( alpha -> alpha ) ;
       --- twice ( f ) <= lambda ( x ) => f ( f ( x ) ) ;


  "twice" defines a new function that has a  single  argument  and  some  other
  function  "f"  bound into its definition.  The new function has the same type
  as "f".  We can see its effect using a simple function like "square":


       twice ( square ) ;
       lambda ( x ) => square( square ( x ) ) : num -> num

       twice ( square ) ( 3 ) ;
       81 : num








  Hope Tutorial                                                         Page 30










  The new function applies the bound-in function to its argument twice.  We can
  even  bind  in  "twice"  itself,  generating a new function that behaves like
  "twice" except that the function eventually bound in  will  be  applied  four
  times:


       twice ( twice ) ;
       lambda ( x ) => twice ( twice ( x ) )
       : ( alpha -> alpha ) -> ( alpha -> alpha )

       twice ( twice ) ( square ) ( 3 ) ;
       43046721 : num











































  Hope Tutorial                                                         Page 31










                                  In conclusion

  In this article you've been introduced to the ideas of functional programming
  through  one  of  the  new generation of functional languages.  You saw how a
  Hope program is just a series of functions that are regarded  as  definitions
  of  parts  of  a  data structure - the 'results' of the program - and how the
  powerful idea of higher-order functions allows  us  to  capture  many  common
  program patterns in a single function.


  Some of these ideas will already be familiar  to  users  of  LISP,  but  they
  appear  in a purer form in Hope, because there are no mechanisms for updating
  data structures like LISP's SETQ and RPLACA or for specifying  the  order  of
  evaluation  like  GO  and PROG.  Unlike LISP programs, Hope programs are free
  from side-effects  and  possess  the  mathematical  property  of  referential
  transparency.


  You also saw features that are primitive or  lacking  in  LISP  and  in  most
  imperative  languages.   The  data  declaration  lets you define complex data
  types without worrying about how they're represented  and  pattern-  matching
  lets  you decompose them, so you can use abstract data types directly without
  writing access procedures and without the need to invent lots of  new  names.
  The  typing  mechanism lets the compiler check that you're using data objects
  in a correct and consistent way, while the idea of  polymorphic  types  stops
  the  checking  from  being  too  restrictive  and lets you define common data
  'shapes' with a single function.


  Higher-order functions and polymorphic types allow us to write programs  that
  are  very  concise.   Programmers  are more productive and their programs are
  easier to understand and  to  reason  about.   The  property  of  referential
  transparency  improves our ability to reason about programs still further and
  makes it possible to transform them mechanically into programs that are still
  provably correct, but more efficient in their use of space or time.  Finally,
  referential transparency keeps the meaning of Hope  programs  independent  of
  the  order they're evaluated in, making them ideal for parallel evaluation on
  suitable machines.  You'll be seeing a lot more of Hope and languages like it
  in the future.
















  Hope Tutorial                                                         Page 32



