Tutorial

Getting started
Datum expressions
Shape expressions
Array expressions
Array variables
Commands
Conditionals
Binding constructs
Functions
The standard prelude
Second order Functions
Recursions
Loading Files
Modes
Shell Commands

There is another tutorial for FISh 1.0 by B. Molinari.

Getting started

The FISh language embodies a new approach to programming centred on shapes, the structural aspect of data structures. An overview of the theory and design principles underpinning FISh can be found in

Poly-dimensional array programming

You can also find some reference material in the Reference directory.
At a minimum you will probably want to take a look at the FISh type system.

This section provides a quick demo to show what the language is about. Later sections examine the language constructs in more detail. Running "fish" starts up the FISh shell, which loads some startup code, and then greets you with

Welcome to FISh v. 1.6
(C) Copyright 1998, C. Barry Jay
No warranty expressed or implied
See README for details
>-|>

>-|> is the FISh prompt. You can enter FISh terms and bind variables to them in the shell environment. The syntax is

variable_name = fish_term;;

So to bind the variable x to the integer 3, we enter

>-|> let x = 3 ;;

and the shell responds with

x : size
#x = 3

The responses tells us that x is bound to a term of size type, and whose shape #x is 3 . Sizes are integers known to the compiler, used to describe compile-time constants such as the lengths of arrays, etc. The shape of a size is itself. We can turn the number 3 into an integer by declaring its type

>-|> let y = (3:int) ;;
y : int

Note that this time the shape is not given. This is because all integers have the same shape. We can recover the shape int_shape by asking for it explicitly:

>-|> #y ;; 
J : #int
#J = int_shape

Since #y was not given a name, it is merely the most recently caught fish, denoted by the "FISh hook" J. Here is a vector:

>-|> let v = fill {3:int_shape} with [0,1,2];;
v : [int]
#v = { 3 : int_shape }

Its type [int] is that of an array of integers. Its shape {3:int_shape} is that of a vector of length 3 whose entries have integer shape. Here are two more arrays

>-|> let mat = fill {2,3:int_shape} with [0,1,2,3,4,5];;
mat : [int]
#mat = { 2,3 : int_shape }
>-|> let vecvec = fill  {2:3:int_shape} with [0,1,2,3,4,5];;
vecvec : [[int]]
#vecvec = { 2 : 3 : int_shape }

mat is a 2x3 matrix of integers. Like v its type is that of an array of integers. Its shape reveals its structure, to be a matrix. vecvec looks very similar to mat but it is a vector of vectors, i.e. an array of arrays of integers, of type [[int]]. Its shape shows it to be a vector of length 2, whose entries are vectors of length 3, of integers. We can define a function by

>-|> let f x = x*x;;
f : int -> int

and then map this across arrays, such as v and mat.

>-|>  let mat2 = map f mat;;
mat2 : [int]
#mat2 = { 2,3 : int_shape }
>-|> %run mat2;;
fill { 2,3 : int_shape }
with [
  0,1,4,
  9,16,25
]

The shape analyser in the compiler determines that mat2 is a 2x3 matrix of ints. The actual values of the entries are computed by invoking the run command. In more detail, the declaration of mat2 causes its partial evaluation to a program in the sub-language of FISh called Turbot. You can see the turbot code by the shell command

>-|> %turbot mat2;;
newvar (succdim 2 (succdim 3 (zerodim int_shape)))
(fun A ->
  seq
  (newvar (succdim 2 (succdim 3 (zerodim int_shape)))
  (fun B ->
    seq
    (seq (assign get(sub(sub(B,(0 :int)),(0 :int))) (0 :int))
    (seq (assign get(sub(sub(B,(0 :int)),(1 :int))) (1 :int))
    (seq (assign get(sub(sub(B,(0 :int)),(2 :int))) (2 :int))
    (seq (assign get(sub(sub(B,(1 :int)),(0 :int))) (3 :int))
    (seq (assign get(sub(sub(B,(1 :int)),(1 :int))) (4 :int))
    (seq (assign get(sub(sub(B,(1 :int)),(2 :int))) (5 :int)) skip))))))
    (forall (0 :int) (2 :int)
    (fun i -> forall (0 :int) (3 :int)
      (fun j -> assign get(sub(sub(A,i),j))
        (get(sub(sub(B,i),j)) * get(sub(sub(B,i),j))))))))
  (output A))

The run command translates the Turbot program into C and stores it in a file called mat2.c. Here is the C code for mat2.

/* translated by fish */

#include 
#include 
#include 
#include 
#include 

#include "fish.h"

int _argc;
char **_argv;


int main(int argc,char *argv[]) {
  _argc = argc;
  _argv = argv;
  
  { int A[2][3];
    { int B[2][3];
      B[0][0] = 0;
      B[0][1] = 1;
      B[0][2] = 2;
      B[1][0] = 3;
      B[1][1] = 4;
      B[1][2] = 5;
      { int i;
        for (i = 0; i < 2; i++) {
          { int j;
            for (j = 0; j < 3; j++) {
              A[i][j] = (B[i][j]*B[i][j]);
            }
          }
        }
      }
    }
    fish_print(_argc,_argv,INT_SHAPE,2,3,ARRAY_BOUNDARY,END_OF_SHAPE,(char *)A);
  }
  return 0;
}

The main function creates two matrices A and B of the appropriate types and sizes, initialises B to be mat and then runs a doubly nested for-loop to place the results of the mapping into A. Note that the number of for-loops and their bounds have been inferred by shape analysis. Note, too, that B is initialised outside the loops, not within them, as might occur in a naive implementation.

Here map is itself a term, of type

 
map : (a -> b) -> [a] -> [b]

When the function being mapped has the same type for its results as its arguments, then you can use a variant form of mapping, called

selfmap : (a -> a) -> [a] -> [a]

which has a restricted type. selfmap will use the same storage for the argument and the result if it is safe to do so. There are two safety issues: aliasing (a clash over storage use) and shaping (that the result has the same shape as the argument). For example, the C code for selfmap f mat2 is

/* translated by fish */

#include 
#include 
#include 
#include 
#include 

#include "fish.h"

int _argc;
char **_argv;


int main(int argc,char *argv[]) {
  _argc = argc;
  _argv = argv;
  
  { int A[2][3];
    A[0][0] = 0;
    A[0][1] = 1;
    A[0][2] = 2;
    A[1][0] = 3;
    A[1][1] = 4;
    A[1][2] = 5;
    { int i;
      for (i = 0; i < 2; i++) {
        { int j;
          for (j = 0; j < 3; j++) {
            A[i][j] = (A[i][j]*A[i][j]);
          }
        }
      }
    }
    fish_print(_argc,_argv,INT_SHAPE,2,3,ARRAY_BOUNDARY,END_OF_SHAPE,(char *)A);
  }
  return 0;
}

The distinction between mat and vecvec is important for maping. For example,

>-|> map f vecvec;;
Error unifying [[int]] and [float]

produces a type error, as the entries of vecvec are vectors, not integers. However, we can map array functions over vecvec:

>-|> let sum = fold plus_int 0;;
sum : [int] -> int
>-|> let v3 = map sum vecvec;;
v3 : [int]
#v3 = { 2 : int_shape }
>-|> %run v3;;
fill { 2 : int_shape }
with [
  3,12
]

fold is the usual fold of lists now applied to arrays, so that sum adds up the entries of the array. Here is the main function from the C code for v3.

/* translated by fish */

#include 
#include 
#include 
#include 
#include 

#include "fish.h"

int _argc;
char **_argv;


int main(int argc,char *argv[]) {
  _argc = argc;
  _argv = argv;
  
  { int A[2];
    { int B[2][3];
      B[0][0] = 0;
      B[0][1] = 1;
      B[0][2] = 2;
      B[1][0] = 3;
      B[1][1] = 4;
      B[1][2] = 5;
      { int C;
        { int i;
          for (i = 0; i < 2; i++) {
            { int D[3];
              memcpy(D,B[i],sizeof(D));
              C = 0;
              { int j;
                for (j = 0; j < 3; j++) {
                  C = (C+D[j]);
                }
              }
            }
            A[i] = C;
          }
        }
      }
    }
    fish_print(_argc,_argv,INT_SHAPE,2,ARRAY_BOUNDARY,END_OF_SHAPE,(char *)A);
  }
  return 0;
}

Note how a single auxilary variable is used to hold all of the partial sums. This only happens if the shape of the right-hand sides, here C+D[j] is the same as that of the left-hand side. Otherwise, new storage must be allocated for each intermediate result.

Datum expressions

Integers and floats are written in the usual way. Coercion from integers to floats are given by int2float. It is desirable to make this coercion explicit as integers and floats have different shapes. The boolean values are true and false. Characters are written between single quotes, e.g. 'a'. The following escaped characters are also accepted, again with their standard meanings.

 \b,\n,\r,\t,\'

Strings are represented by arrays of characters. These can be constructed just like other arrays, but also support the usual string syntax, e.g. "Abc\nd's." The comparison operations

 =, <,<=,>,>=,

can be applied to datum values of any type, with the usual ordering (ascii for characters). These overloaded operations are distinguished during type inference. The basic arithmetic operations, negation

and the infix, binary operations

 +,-,*

can be applied to either integers or floats, but not a mixture of the two. If neither argument has known type then both are assumed to be integers. Integer division and modulus are given by the infix operations

 div,mod

The unary operation -. and the infix operations

 +.,-.,*.,/.,/,=.,<.,<=.,>.,>=.

are specifically for floats (note both /. and / for division). Many of the standard mathematical functions are also available, and like the operations above, must be supplied with their arguments, e.g. sin 2.4. Binary operations are written infix. The usual precedence rules for operations apply.

Shape expressions

FISh is designed to allow naming and computations on shapes. Every datum value is also of the corresponding shape type, also called a static type (as in the two-level lambda calculus), e.g.

3:size
4.2:cost
true:fact
'a':mark

Such values take static types by default, and are implicitly coerced to be of the corresponding dynamic type as and when necessary. Dynamic types can be forced by giving explicit types, as with x and y above. The basic operations will return a static type for their result if all the arguments are static - otherwise the result will be dynamic, e.g. 3+4:size but 3+(4:int):int. Each datum type delta has a corresponding shape type #delta which has a single value delta_shape. For example, int_shape : #int.

Array Shapes

FISh arrays are regular finite-dimensional arrays, where regular means they are rectangular, and that all their entries have the same shape. Their shape is determined by a list of sizes, representing the array size in each dimension, and the common shape of all the entries. For example, the shape

 {2,3:int_shape}

is the shape of a 2x3 matrix of integers. The list of sizes is from outermost to innermost. For matrices, we conventionally consider them to be columns of rows.

FISh supports, and actively exploits, the ability to construct arrays of arrays. For example,

 { 7,6:3,3:float_shape}

is the shape of a 7x6 matrix of 3x3 matrices of floats. Such an array may appear as a block decomposition of a large matrix, or as an array of neighbourhoods, each 3x3 array representing the nearest neighbours of a single entry.

Constants Equality of array shapes is given by the infix operator #=. Here are the other constants for manipulating array shapes.

zerodim sh #= {:sh}
undim {:int_shape } #= int_shape
succdim 7 {6:sh} #= {7,6:sh}
lendim {3,2:sh } = 3
preddim {3,2:sh } #= {2:sh}
numdim {4,3:sh} = 2

There is also a complete list of FISh constants.

Array expressions

There are several means of constructing an array expression in FISh. The most direct is to specify its shape and data using the fill .. with .. syntax. For example,

	
>-|> let a1 = fill {3:int_shape} with [4,5,6] ;; 
a1 : [int]
#a1 = { 3 : int_shape }

produces an integer array of length 3 whose entries are 4,5, and 6. Similarly,

>-|> let a2 = fill {2,3:int_shape} with [4,5,6,7,8,9];;
a2 : [int]
#a2 = { 2,3 : int_shape }
>-|> %run a2;;
fill { 2,3 : int_shape }
with [
4,5,6,
7,8,9
]

defines a matrix and

>-|> let a3 = fill {:int_shape} with [5];;
a3 : [int]
#a3 = { : int_shape }

defines a zero dimensional array. Just as a one dimensional array can be thought of as a line segment, or vector, a zero dimensional array can be construed a point with a single associated value. Such arrays should not be confused with the value of its unique entry (which has a different type) nor with the vector of length one, namely

>-|> let a4 = fill {1:int_shape} with [5];;
a4 : [int]
#a4 = { 1 : int_shape }

Nested arrays can be defined in the same manner, e.g.

>-|> let a5 = fill {2:3:int_shape} with [4,5,6,7,8,9];;
a5 : [[int]]
#a5 = { 2 : 3 : int_shape }
>-|> %run a5;;
fill { 2 : 3 : int_shape }
with [
4,5,6,
7,8,9
]

produces a vector (of length 2) of vectors (of length 3) of integers.

Another method of constructing arrays is to build them from existing datum or array values directly. (These constructions may not be supported in future versions of the language.) For example,

>-|> let b1 = [2] ;;
b1 : [int]
#b1 = { : int_shape }

produces a zero-dimensional matrix whose sole entry is 2. However, identifiers of array type can be used, too. For example,

>-|> let b2 =  [a1] ;;
b2 : [[int]]
#b2 = { : 3 : int_shape }

uses the vector a as the sole entry. The other basic mechanism is to construct an array from its sub-arrays. For example,

>-|> let b3 =  | b2 ; b2 | ;;
b3 : [[int]]
#b3 = { 2 : 3 : int_shape }

creates a vector of length 2 whose entries are both copies of b2. Here are a couple of other examples:

	
>-|> let mat1 = | | [2]; [3] | ; 
                  | [7]; [9] | |;;
mat1 : [int]
#mat1 = { 2,2 : int_shape }
>-|> let mat2 = | | [4]; [5] | ; 
	          | [6]; [7] | |;;
mat2 : [int]
#mat2 = { 2, 2 : int_shape }

Both mat1 and mat2 have the same shape, { 2,2 : int_shape }. Note that the integers must first be converted to zero-dimensional arrays, and then incorporated into higher-dimensional structures. FISh provides some array operations, such as sub-array extraction. We can write

>-|> let v1 = sub(mat1,0)
v1 : [int]
#v1 = { 2 : int_shape }

to take a subarray of mat1 , that is, its zeroth row.

>-|> %run v1;;
fill { 2 : int_shape }
with [
  2,3
]

To extract the first entry of v1 requires two more steps, as follows.

>-|> let v2 = get (sub(v1,1));;
v2 : int
>-|> %run v2;;
3

This process of extraction can be given directly by

>-|> let v2 = mat1[0,1];;
v2 : int
>-|> %run v2;;
3

Note, however, that this notation always invokes a get, and only works for extracting entries, not sub-arrays, e.g.

>-|> mat1[0];;
J : int
shape error -- 
succdim 2 (zerodim int_shape)
cannot have undim applied

produces a shape error. The error message indicates the source of the error. Pretty printing of these terms requires some further work.

Array variables

The array expressions above cannot be assigned to - they are referentially transparent . Formally, the array types a written above are short forms for exp a the type of expressions whose value is an a . By contrast, array variables, which can be assigned to, and have their value of type a extracted are of type var a . Creation of array variables is handled below, under "Binding Constructs". This section considers their manipulation.

If x : var int is an integer variable then

x := x +1

increments x by 1. The x on the right is coerced to represent the value of x which is also written as !xThus the assignment above may also be written

x := !x +1

The notation for extracting sub-arrays and entries of array expressions also operates on array variables, and returning variables as their results. For example, if y: var [int] then get y : var int, sub(y,0) : var [int] and y[0] : int are all variables, though they cannot all be well-shaped. This ability to assign to both an array, and its entries is one of the features that distinguishes FISh from other Algol-like languages. It works because the compiler is able to check that the shape of the variable being assigned to matches the shape of the proposed value. If not then a shape error is recorded.

Constants

assign x t = x:= t is the variable assignment.
get x is the variable representing the sole entry of x.
sub 3 x is the variable representing the third entry of x

Commands

FISh supports the fundamental imperative features, based on the type comm of commands. Like values of a given datum type, well-shaped commands all have the same shape. Rather than create yet another singleton type, say #comm it has proved convenient to make the common command shape be true:fact. Such shapes are not reported by the compiler unless there is a shape error.

The basic command of assignment is introduced in the section on array variables above. The other fundamental command is the operator output. It is used to print the value of an expression of datum type (integer, float, or boolean), or an array of such types, of any dimension. When output is applied to such an expression, the application is of command type.

The semi-colon is used for sequencing commands: C;D performs C then D. skip and abort have their usual meanings.

>-|> output true;;
J : comm
>-|> %run J;;
true

(The output command is invoked automatically when %run is applied to an expression.)

The format of for-loops is illustrated by the following example

>-|> for 1 <= i < 5 do output i done;;
J : comm
>-|> %run J;;
1
2
3
4

Currently, the lower bound must be given by "<=" and the upper bound by "<". The loop body must be a command. When the lower bound for the loop is 0 then it may be omitted, as in:

>-|> for i < 4 do output i done;;
J : comm
>-|> %run J;;
0
1
2
3

For iteration that may be unbounded, FISh also has a while-loop:

>-|> new x = 0 
     in 
     while x < 8 do 
x := x + 2; 
        output x 
             done
     end;; 
J : comm
>-|> %run J;;
2
4
6
8

This example uses a local variable x whose meaning is discussed in the following section.

Constants

output t prints the value of t.
seq C D = C;D
skip
abort
cond b C D = if b then C else D
forall m n P = for m <=i < n do P i done
whileTrue b C = while b do C done

Conditionals

Conditional syntax is now the standard if .. then .. else .. format. However, there are three different rules for typing a conditional. If the condition can be typed as a fact i.e. is known to the compiler, then the branches can be of any type whatsoever. For example, if f and g are functions of the type int -> int then

if true then f else g : int -> int

However, if the condition is dynamic, i.e. of type bool, then the branches must either be commands or expressions, with commands as the default type. For example,

>-|> let f x y = if x then y else y;;
f : bool -> comm -> comm
>-|> let g x = if x then 3 else 4;;
g : bool -> int

Now let us consider the shape of a conditional. When the condition is a fact then the branch taken is known statically, and so its shape is that of the condition. When the condition is not known until run-time, the shape could be that of either branch, so we require that these be the same. For commands, this is relatively easy, since all well-shaped commands have the same shape. For example,

>-|> let c = new b = true in if b then skip else abort end;;
c : comm
>-|> let d = new b = true in if b then skip else error end ;;
d : comm
shape error -- 
error
appears explicitly

let v = if (true:bool)  
        then (fill {2:int_shape} with [0,1])
        else (fill {3:int_shape} with [2,3,4])
;;
v : [int]
shape error -- 

succdim 2 (zerodim int_shape)
and
succdim 3 (zerodim int_shape)
are different shapes for branches of a datum conditional

This rather daunting error message is not well expressed, but at least it tells you whereabouts the problem has occured (instead of merely reporting the existence of an error). Sometimes the error may be hidden within a function definition. For example,

 
>-|> let h x = if x then fill {3:int_shape} with [0,1,2] 
else fill {2:int_shape} with [6,6];;
h : bool -> [int]
>-|> h true;;
J : [int]
shape error -- 

succdim 3 (zerodim int_shape)
and
succdim 2 (zerodim int_shape)
are different shapes for branches of a datum conditional

The actual shape of h is fun x -> error . This constraint on conditionals is rather mild: there is no restriction on conditionals with static tests, or on those whose branches are either commands or expressions of datum type. The restrictions only arise when constructing a conditional whose branches are either proper arrays, or functions.

Binding Constructs

There are several ways of binding values to variables in FISh. We have already seen the use of let declarations in the shell. Now let us consider bindings applicable within a phrase.

The most general form of binding is the polymorphic where-clause, e.g.

>-|> let y = x + x 
where x = 3 ;;

Note that x here is local to the definition of y. Evaluation of where clauses is call-by-name. More precisely, the expression for x is inlined during compilation to produce

>-|> let y = 3 + 3;;

FISh also supports a let-form for where clauses, so that

>-|> let y = let x = 3 in x + x;;

is translated to the where-clause above.

Both where- and let-clauses allow you to define multiple bindings separated by and:

 >-|> let f x = x + 3 
and g y = y * 2 
      in (f . g) 5;;
 J : int
 #J = int_shape
 >-|> %run J;;
 13

When building such lists of bindings, inner bindings may depend on outer bindings. Future work may change this so that no dependencies are allowed.

The other binding forms introduce a local variable indicated by the keyword new. There are two fundamental forms:

new #x = sh in C end 
new #x = sh in C return x

In each case sh is an array shape, the shape of the local variable x, and C is a command possibly using x . The first form is itself a command. The second is an expression being the value of x after executing C. For example,

  >-|> let v = new #x = {3:int_shape} in
       for i<3 do 
 x[i] := i
       done 
       return x ;;  
       v : [int]
       #v = { 3 : int_shape }
       >-|> %run v;;
       fill { 3 : int_shape }
       with [
         0,1,2
       ]

Several extensions of this syntax are supported. First, the new declaration may initialise the variable at the same time as declaring its shape. For example,

  >-|> let v = new x = fill {3:int_shape} with [0,1,2] in 
       C
       return x ;;

is syntactic sugar for

  >-|> let v = new #x = {3:int_shape} in 
       x[0] := 0 ;
       x[1] := 1 ;
       x[2] := 2 ;
       C
       return x ;;

This convention means that FISh supports both "by name" and "by value" evaluation of array expressions. For example,

      new x = e in C end

evaluates x by value, while

 
      let x = e in C

evaluates x by name. Note however, that "by value" evaluation is only for arrays, not functions or commands. Second, several variables may be declared in the same block, with the declarations separated by and. These are converted into nested blocks, so that later declarations may depend on the shapes of the earlier ones, e.g.

 >-|> new x = | [7]; [8]; [9] | 
 and #y = #x 
 and z = x
 in
 y := z;
 output y
 end;;
 J : comm
 >-|> %run J;;
 fill { 3 : int_shape }
 with [
   7,8,9
 ]

Here, we've initialized x, given y the same shape as x, and initialized z with x's initial value. In the block body, we assign z's initial value to y, and print it.

To summarise, where- and let-clauses can be used to bind arbitrary phrases, but will be evaluated by name. new blocks can be used to declare and initialise local array variables. all shape expressions are evaluated by the compiler anyway. Thus call-by-value evaluation is available for expressions, but not for functions.

Constants

let x = s in t is sugar for t where x = s
new #x = sh in P x end is sugar for newvar sh P
new #x = sh in P x return x is sugar for newexp sh P

Functions

If we type

>-|> let f = fun x -> x + 5;;

then the system responds

f : int -> int

indicating that the function f takes an integer argument, and produces an integer result. The shape of a function is a function of shapes. We follow the normal practice of not displaying values of functions, so that function shapes are not reported. The syntax for functions just given is useful when they are used as arguments. Alternatively, we could have bound f to the same function by writing

>-|> let f x = x + 5;;

In FISh, all functions are "curried", so if we enter

>-|> let g x y = 2 * x + 5 * y;;

the system tells us

g : int -> int -> int

Equivalently, we could have written

let g = fun x -> fun y -> 2 * x + 5 * y;;

Functions may be composed using a "dot":

    >-|> let h = g . f;;
    h : int -> int -> int

The function h is f followed by g.

>-|> h 3 4;;
        J : int
#J = int_shape
        >-|> %run J;;
        36

The standard prelude

The core of FISh only supports a small number of primitives. Many of the standard operations and functions are built into a the FISh source program standard_prelude.fsh which is loaded automatically when the fish command is given. It introduces a number of useful constants and functions, e.g. doall procedures for applying a procedure to each entry of an array. You can write re-define any of the functions in the standard prelude, but you do so at your own risk!

Second-order functions

Among them are many of the standard second order functions of the Bird-Meertens Formalism adapted for array programming. Their definitions in terms of FISh primitives can be found in the prelude, together with some brief comments about their construction. Aside from fold , they all compile into (nested) for-loops which execute efficiently. This page will illustrate their use. Other operations special to arrays, such as transpostion, will be explained elsewhere.

Map

        map : (a -> b) -> [a] -> [b]

takes a function f and an array x and maps the function across the array. For example

        >-|> let f x = x + 1 ;;
        f : int -> int
        >-|> let x = fill {2,2:int_shape} with [3,4,5,6] ;;
        x : [int]
        #x = { 2,2 : int_shape }
        >-|> let y = map f x;;
        y : [int]
        #y = { 2,2 : int_shape }
        >-|> %run y;;
        fill { 2,2 : int_shape }
        with [
          4,5,
          6,7
        ]

There is also selfmap as mentioned above, which will perform the mapping in place if appropriate.

Reduce

We can reduce an array with a function using reduce

        reduce : (a -> b -> a) -> a -> [b] -> a

The first parameter is a function to be applied to an accumulated intermediate result and an element of the array; the second parameter is an initial value for the accumulator. The function is applied to array entries in increasing order of index (so reduce acts like a "left fold"). Example:

 >-|> reduce plus_int 0 (fill {3:int_shape} with [1,5,9]);;
 J : int
 #J = int_shape
 >-|> %run J;;
 15

Note that reduce accumulates its intermediate values in a single piece of storage. This is most efficient, but imposes the constraint that the function being reduced preserves the shape of its first argument. This is automatic for datum functions but means that one cannot reduce a shape-changin function, such as append. For this a general fold is required.

Fold

fold has the same type as reduce

        fold : (a -> b -> a) -> a -> [b] -> a

and will be replaced by it when the shapes allow. In the fairly rare cases where reduction is inappropriate for shape reasons, the fold is interpreted using a primitive recursion. Like all primitive recursions it is unwound by the compiler, which may consume a lot of space.

Zip

zipop zips together two arrays of the same shape and applies its function argument to corresponding entries.

 zipop : (a -> b -> c) -> [a] -> [b] -> [c]

For example,

 >-|> zipop plus_int (fill {3:int_shape} with [1,2,3]) 
(fill {3:int_shape} with [4,5,6]) ;; 
 J : [int]
 #J = { 3 : int_shape }
 >-|> %run J;;
 fill { 3 : int_shape }
 with [
   5,7,9
 ]

Reverse

The reverse function takes an array and reverses the entries in the outermost dimension of the outermost layer:

   >-|> let v = fill { 3,2 : int_shape } with [1,2,3,4,5,6];;
         v : [int]
         #v = { 3,2 : int_shape }
         >-|> %run v;;
         fill { 3,2 : int_shape }
         with [
           1,2,
           3,4,
           5,6
         ]
         >-|> let vrev = reverse v;;
         vrev : [int]
         #vrev = { 3,2 : int_shape }
         >-|> %run vrev;;
         fill { 3,2 : int_shape }
         with [
           5,6,
           3,4,
   1,2
         ]

Copy

We can build an array of a given shape with identical entries using copy:

        >-|> copy { 3 : int_shape } 0;;
        J : [int]
        #J = { 3 : int_shape }
        >-|> %run J;;
        fill { 3 : int_shape }
        with [
          0,0,0
        ]

Given a shape, copy only uses the dimensions in the outermost layer, and ignores the underlying data type in the shape:

    >-|> copy { 3,4 : 2 : float_shape } 0;;
         J : [int]
         #J = { 3,4 : int_shape }

Recursions

FISh supports both primitive recursion and general recursion, in addition to the for- and while-loops mentioned above. Primitive recursion takes the form

        primrec f x n

where f : size -> V -> V is a function from V to V which takes a size as first parameter, x is the argument, and n (or any other size) is the number of iterations required. For example,

        >-|> let f (n:size) x = n + x ;;
        f : size -> int -> int
        >-|> let k = primrec f 0 4;;
        k : int
        #k = int_shape
        >-|> %run k;;
        6

k is 3+2+1+0+0 = 6.

Recursive commands and functions are defined using the let rec construct. The simplest example is:

        >-|> let rec f = f;;
        f : comm

This is just an infinite loop, so we won't try to run it! As shown, let rec can be used to create bindings in the shell.

We can also write FISh terms using let rec. For example, here is the factorial function:

        >-|> let factorial n = 
               new y = 1 in 
               let rec f x = 
                     if x = 0 then skip 
                     else y := y * x ; f (x-1)
               in f n
               return y;;
        factorial : int -> int

The body of a function defined using let rec must be a command, such as an assignment or output. The form let rec has a where rec equivalent:

        >-|> let factorial2 n = 
               new y = 1 in 
               f n
                 where rec f x = 
                    if x = 0 then skip 
                    else y := y * x ; f (x-1)
               return y;;
        factorial2 : int -> int

As for let and where , let rec and where rec allow multiple definitions separate by semicolons. Nonrecursive and recursive definitions may be mixed in such lists:

        >-|> let rec f = f ; 
                     g x = x + 3 
               in 
                 if factorial 7 > 42 
                 then f 
                 else output (g 19);;
        J : comm

Constants fix P = let rec x = P x

Phrase polymorphic constants

There are some additional phrase polymorphic constants. error is the polymorphic shape error. shape also written # is the shape combinator and null is its partial inverse

        #(null sh) = sh

null sh is the value of an array that has been declared to be of shape sh but not yet initialised.

Constants

primrec f x n
error
shape t = #t

Loading files

By now, you're ready to try your hand at writing FISh programs. Look at standard_prelude.fsh, the startup file, for more examples. You can use the shell directly, as we've done in the examples. If you're writing programs of any length, it's more convenient to put your definitions into a file and load the file from the shell. The syntax is

 >-|> %use "mycode.fsh";;

The shell prints the types of functions as they are loaded.

Modes

Various diagnostic tools are available through mode switches, whose syntax is

%show + mode

or %show - mode where mode is a mode name (or a prefix of one. The available modes and their default settings are:

  "parse",Show_off ;      (* do not display parse trees *)
  "infer",Show_off ;      (* do not display inferred term *)
  "loop_opt",Show_on ;    (* do lift newvar from loops  *)
  "datum_opt",Show_on ;   (* do lift newexp from datum operations *)
  "assign_opt",Show_on    (* do lift newexp from assignments *)

parse shows the parsed term and is mainly for diagnostic purposes.
infer shows the term after type inference. The main point is that inference will insert some explicit coercions. For example, the size 2 must be coerced to be an integer in forall 2.
```
>-|> %show + infer;;
>-|> forall 2;;
Inferred term : 
forall (2 :int)
J : int -> (int -> comm) -> comm
```
loop_opt, datum_opt and assign_opt are three standard optimisations, as explained in thelanguage definition. There is no point in switching them off unless experimenting with the implementation.

Other shell commands

You have seen various shell commands during this tutorial. Here is a complete list.

let x = t ;; declares the identifier x to be t.
%turbot x;; shows the turbot term for x.
%run -[qc] x;; evaluates x. The option -q supresses output to screen. The option -c compiles C code without executing it.
%show [+-] m switches the mode m. An unambiguous prefix of the mode name will suffice, e.g. %show + i;; will show inferred terms.
%use f;; will load the file f.
%quit;; will exit the system.

Good FIShing!

Please feel free to send any comments.

Tutorial

Contents

Map

Reduce

Fold

Zip

Reverse

Copy

Phrase polymorphic constants

Good FIShing!