_B_e_r_k_e_l_e_y _F_P _U_s_e_r'_s _M_a_n_u_a_l, _R_e_v. _4._1 _b_y _S_c_o_t_t _B_a_d_e_n _A_B_S_T_R_A_C_T _T_h_i_s _m_a_n_u_a_l _d_e_s_c_r_i_b_e_s _t_h_e _B_e_r_k_e_l_e_y _i_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _B_a_c_k_u_s' _F_u_n_c_t_i_o_n_a_l _P_r_o_g_r_a_m_m_i_n_g _L_a_n_g_u_a_g_e, _F_P. _S_i_n_c_e _t_h_i_s _i_m_p_l_e_m_e_n_t_a_t_i_o_n _d_i_f_f_e_r_s _f_r_o_m _B_a_c_k_u_s' _o_r_i_- _g_i_n_a_l _d_e_s_c_r_i_p_t_i_o_n _o_f _t_h_e _l_a_n_g_u_a_g_e, _t_h_o_s_e _f_a_m_i_l_i_a_r _w_i_t_h _t_h_e _l_i_t_e_r_a_t_u_r_e _w_i_l_l _n_e_e_d _t_o _r_e_a_d _a_b_o_u_t _t_h_e _s_y_s_t_e_m _c_o_m_m_a_n_d_s _a_n_d _t_h_e _l_o_c_a_l _m_o_d_i_f_i_c_a_t_i_o_n_s. 9 _A_u_g_u_s_t _2_7, _1_9_8_7 9 PS2:7-4 Berkeley FP User's Manual, Rev. 4.1 _1. _B_a_c_k_g_r_o_u_n_d FP stands for a _F_u_n_c_t_i_o_n_a_l _P_r_o_g_r_a_m_m_i_n_g language. Func- tional programs deal with _f_u_n_c_t_i_o_n_s instead of _v_a_l_u_e_s. There is no explicit representation of state, there are no assignment statments, and hence, no variables. Owing to the lack of state, FP functions are free from side-effects; so we say the FP is _a_p_p_l_i_c_a_t_i_v_e. All functions take one argument and they are evaluated using the single FP operation, _a_p_p_l_i_c_a_t_i_o_n (the colon ':' is the apply operator). For example, we read +:<3 4> as "apply the function '+' to its argument <3 4>". Functional programs express a functional-level combina- tion of their components instead of describing state changes using value-oriented expressions. For example, we write the function returning the _s_i_n of the _c_o_s of its input, i.e., _s_i_n(_c_o_s(_x)), as: sin@cos. This is a _f_u_n_c_t_i_o_n_a_l _e_x_p_r_e_s_s_i_o_n, consisting of the single _c_o_m_b_i_n_i_n_g _f_o_r_m called _c_o_m_p_o_s_e ('@' is the compose operator) and its _f_u_n_c_t_i_o_n_a_l _a_r_g_u_m_e_n_t_s _s_i_n and _c_o_s. All combining forms take functions as arguments and return functions as results; functions may either be applied, e.g., sin@cos:3, or used as a functional argument in another functional expression, e.g., _t_a_n @ _s_i_n @ _c_o_s. As we have seen, FP's combining forms allow us to express control abstractions without the use of variables. The _a_p_p_l_y _t_o _a_l_l functional form (&) is another case in point. The function '& exp' exponentiates all the elements of its argument: 9 (1.1) 7 &_e_x_p : <_1._0 _2._0> =_ <_2._7_1_8 _7._3_8_9> 9In (1.1) there are no induction variables, nor a loop bounds specification. Moreover, the code is useful for any size argument, so long as the sub-elements of its argument con- form to the domain of the _e_x_p function. We must change our view of the programming process to adapt to the functional style. Instead of writing down a set of steps that manipulate and assign values, we compose functional expressions using the higher-level functional forms. For example, the function that adds a scalar to all elements of a vector will be written in two steps. First, the function that distributes the scalar amongst each ele- ment of the vector: 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-5 (1.2) 7 _d_i_s_t_l : <_3 <_4 _6>> =_ <<_3 _4> <_3 _6>> 9Next, the function that adds the pairs of elements that make up a sequence: 9 (1.3) 7 &+ : <<_3 _4> <_3 _6>> =_ <_7 _9> 9 In a value-oriented programming language the computa- tion would be expressed as: 9 (1.4) 7 &+ : _d_i_s_t_l : <_3 <_4 _6>>, 9which means to apply 'distl' to the input and then to apply '+' to every element of the result. In FP we write (1.4) as: 9 (1.5) 7 &+ @ _d_i_s_t_l : <_3 <_4 _6>>. 9The functional expression of (1.5) replaces the two step value expression of (1.4). Often, functional expressions are built from the inside out, as in LISP. In the next example we derive a function that scales then shifts a vector, i.e., for scalars _a, _b and a vector _v->, compute _a + _b_v->. This FP function will have three arguments, namely _a, _b and _v->. Of course, FP does not use formal parameter names, so they will be designated by the function symbols 1, 2, 3. The first code segment scales _v-> by _b (defintions are delimited with curly braces '{}'): 9 (1.6) 7 {_s_c_a_l_e_V_e_c &* @ _d_i_s_t_l @ [_2,_3]} 9The code segment in (1.5) shifts the vector. The completed function is: 9 (1.7) 7 {_c_h_a_n_g_e_V_e_c &+ @ _d_i_s_t_l @ [_1 , _s_c_a_l_e_V_e_c]} In the derivation of the program we wrote from right to left, first doing the _d_i_s_t_l's and then composing with the _a_p_p_l_y-_t_o-_a_l_l functional form. Using an imperative language, such as Pascal, we would write the program from the outside in, writing the loop before inserting the arithmetic opera- tors. Although FP encourages a recursive programming style, it provides combining forms to avoid explicit recursion. PS2:7-6 Berkeley FP User's Manual, Rev. 4.1 For example, the right insert combining form (!) can be used to write a function that adds up a list of numbers: 9 (1.8) 7 !+ : <_1 _2 _3> =_ 6 The equivalent, recursive function is much longer: 9 (1.9) 7 {_a_d_d_N_u_m_b_e_r_s (_n_u_l_l -> %_0 ; + @ [_1, _a_d_d_N_u_m_b_e_r_s @ _t_l])} The generality of the combining forms encourages hierarchical program development. Unlike APL, which res- tricts the use of combining forms to certain builtin func- tions, FP allows combining forms to take any functional expression as an argument. 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-7 _2. _S_y_s_t_e_m _D_e_s_c_r_i_p_t_i_o_n _2._1. _O_b_j_e_c_t_s The set of objects Z consists of the atoms and sequences <_x918, _x928, . . . , _x9_k8> (where the _x9_i8_Z). (Lisp users should note the similarity to the list structure syntax, just replace the parenthesis by angle brackets and commas by blanks. There are no 'quoted' objects, i.e., 'abc). The atoms uniquely determine the set of valid objects and con- sist of the numbers (of the type found in FRANZ LISP [Fod80]), quoted ascii strings ("abcd"), and unquoted alphanumeric strings (abc3). There are three predefined atoms, T and F, that correspond to the logical values 'true' and 'false', and the undefined atom ?, _b_o_t_t_o_m. _B_o_t_t_o_m denotes the value returned as the result of an undefined operation, e.g., division by zero. The empty sequence, <> is also an atom. The following are examples of valid FP objects: ? 1.47 3888888888888 _a_b "_C_D" <1,<2,3>> <> T <_a,<>> There is one restriction on object construction: no object may contain the undefined atom, such an object is itself undefined, e.g., <1,?> =_ ?. This property is the so-called "bottom preserving property" [Ba78]. _2._2. _A_p_p_l_i_c_a_t_i_o_n This is the single FP operation and is designated by the colon (":"). For a function _Y and an object _x, _Y:_x is an application and its meaning is the object that results from applying _Y to _x (i.e., evaluating _Y(_x)). We say that _Y is the _o_p_e_r_a_t_o_r and that _x is the _o_p_e_r_a_n_d. The following are examples of applications: +:<7,8> =_ 15 tl:<1,2,3> =_ <2,3> 1 :<_a,_b,_c,_d> =_ _a 2 :<_a,_b,_c,_d> =_ _b PS2:7-8 Berkeley FP User's Manual, Rev. 4.1 _2._3. _F_u_n_c_t_i_o_n_s All functions (_F) map objects into objects, moreover, they are _s_t_r_i_c_t: 9 (2.1) 7 _Y:? =_ ?, \/- _YF 9To formally characterize the primitive functions, we use a modification of McCarthy's conditional expressions [Mc60]: 9 (2.2) 7 _p918 -> _e918 ; . . . ; _p9_n8 -> _e9_n8 ; _e9_n+1 99This statement is interpreted as follows: return function _e91 8if the predicate '_p918' is true , . . . , _e9_n8 if '_p9_n8' is true. If none of the predicates are satisfied then default to _e9_n+18. It is assumed that _x, _x9_i8, _y, _y9_i8, _z9_i8_Z. _2._3._1. _S_t_r_u_c_t_u_r_a_l _S_e_l_e_c_t_o_r _F_u_n_c_t_i_o_n_s For a nonzero integer _M, M : _x =_ 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ 0 < _M <_ _k -> _x9_M8; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ -_k<__M<0 -> _x9_k+_M+18; ? pick : <_n,_x> =_ 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ 0 < _n <_ _k -> _x9_n8; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ -_k<__n<0 -> _x9_k+_n+18; ? The user should note that the function symbols 1,2,3,... are to be distinguished from the atoms 1,2,3,.... 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-9 last : _x =_ 9 _x=<> -> <> ; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_1 -> _x9_k8; ? first : _x =_ 9 _x=<> -> <> ; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_1 -> _x918; ? _T_a_i_l _F_u_n_c_t_i_o_n_s tl : _x =_ 9 _x=<_x918> -> <> ; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_ 2 -> <_x928 , . . . , _x9_k8> ; ? 9 tlr : _x =_ 9 _x=<_x918> -> <> ; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_ 2 -> <_x918 , . . . , _x9_k-18> ; ? Note: There is also a function front that is equivalent to tlr. _D_i_s_t_r_i_b_u_t_e _f_r_o_m _l_e_f_t _a_n_d _r_i_g_h_t distl : _x =_ 9 _x=<_y,<>> -> <>; 9 _x=<_y,<_z918, _z928, . . . , _z9_k8>> -> <<_y,_z918>,...,<_y,_z9_k8>>; ? 9 distr : _x =_ 9 _x=<<>,_y> -> <>; 9 _x=<<_y918, _y928, . . . , _y9_k8>,_z> -> <<_y918,_z>,...,<_y9_k8,_z>>; ? 9 9 PS2:7-10 Berkeley FP User's Manual, Rev. 4.1 _I_d_e_n_t_i_t_y 9id : _x =_ _x 9out : _x =_ _x Out is similar to id. Like id it returns its argument as the result, unlike id it prints its result on _s_t_d_o_u_t - It is the only function with a side effect. _O_u_t is intended to be used for debugging only. _A_p_p_e_n_d _l_e_f_t _a_n_d _r_i_g_h_t apndl : _x =_ 9 _x=<_y,<>> -> <_y>; 9 _x=<_y,<_z918, _z928, . . . , _z9_k8>> -> <_y,_z918, _z928, . . . , _z9_k8>; ? 9 apndr : _x =_ 9 _x=<<>,_z> -> <_z>; 9 _x=<<_y918, _y928, . . . , _y9_k8>,_z> -> <_y918, _y928, . . . , _y9_k8, _z>; ? _T_r_a_n_s_p_o_s_e trans : _x =_ 9 _x=<<>,...,<>> -> <>; 9 _x=<_x918, _x928, . . . , _x9_k8> -> <_y918, . . . ,_y9_m8>; ? 9 where _x9_i8 = <_x9_i18, . . . ,_x9_i_m8> //\_\ _y9_j8 = <_x91_j8, . . . ,_x9_k_j8>, 9 1<__i<__k , 1<__j<__m. reverse : _x =_ 9 _x=<> ->; 9 _x=<_x918, _x928, . . . , _x9_k8> -> <_x9_k8, . . . ,_x918>; ? 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-11 _R_o_t_a_t_e _L_e_f_t _a_n_d _R_i_g_h_t rotl : _x =_ 9 _x=<> -> <>; _x=<_x918> -> <_x918>; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_2 -> <_x928, . . . ,_x9_k8,_x918>; ? rotr :_x =_ 9 _x=<> -> <>; _x=<_x918> -> <_x918>; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>_2 -> <_x9_k8, _x918, . . . ,_x9_k-28, _x9_k-18>; ? concat : _x =_ 9 _x=<<_x9118, . . . ,_x91_k8>,<_x9218, . . . ,_x92_n8>,...,<_x9_m18, . . . ,_x9_m_p8>> //\_\ _k, _m, _n, _p > 0 -> <_x9118, . . . ,_x91_k8,_x9218, . . . ,_x92_n8, . . . ,_x9_m18, . . . ,_x9_m_p8>;? Concatenate removes all occurrences of the null se- quence: (2.3) 7 concat : <<1,3>,<>,<2,4>,<>,<5>> =_ <1,3,2,4,5> pair : _x =_ 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>0 //\_\ _k _i_s _e_v_e_n -> <<_x918,_x928>, . . . ,<_x9_k-18,_x9_k8>>; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>0 //\_\ _k _i_s _o_d_d -> <<_x918,_x928>, . . . ,<_x9_k8>>; ? split : _x =_ 9 _x=<_x918> -> <<_x918>,<>>; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>1 -> <<_x918, . . . ,_x9|_k/2|8>,<_x9|_k/2|+18, . . . ,_x9_k8>>;? 9 PS2:7-12 Berkeley FP User's Manual, Rev. 4.1 iota :_x =_ 9 _x=0 -> <>; 9 _xN78+999 -> <1,2,...,_x>; ? _2._3._2. _P_r_e_d_i_c_a_t_e (_T_e_s_t) _F_u_n_c_t_i_o_n_s atom : _x =_ _x _a_t_o_m_s -> T; _x=/?-> F; ? eq : _x =_ _x =<_y,_z> //\_\ _y=_z -> T; _x=<_y,_z> //\_\ _y =/ _z -> F; ? Also less than (<), greater than (>), greater than or equal (>=), less than or equal (<=), not equal (~=); '=' is a synonym for eq. null :_x =_ _x=<> -> T; _x=/? -> F; ? 9length : _x =_ _x = <_x918, _x928, . . . , _x9_k8> -> _k; _x=<> -> 0; ? _2._3._3. _A_r_i_t_h_m_e_t_i_c/_L_o_g_i_c_a_l + : _x =_ _x=<_y,_z> //\_\ _y,_z _a_r_e _n_u_m_b_e_r_s -> _y+_z; ? - : _x =_ _x=<_y,_z> //\_\ _y,_z _a_r_e _n_u_m_b_e_r_s -> _y-_z; ? * : _x =_ _x=<_y,_z> //\_\ _y,_z _a_r_e _n_u_m_b_e_r_s -> _yx_z; ? / : _x =_ _x=<_y,_z> //\_\ _y,_z _a_r_e _n_u_m_b_e_r_s //\_\ _z=/ 0 -> _y/_z; ? _A_n_d, _o_r, _n_o_t, _x_o_r and : <_x,_y> =_ _x=T -> _y; _x=F -> F; ? 9 or : <_x,_y> =_ _x=F -> _y; _x=T -> T; ? 9 xor : <_x,_y> =_ 9 _x=T //\_\ _y=T -> F; _x=F //\_\ _y=F -> F; 9 _x=T //\_\ _y=F -> T; _x=F //\_\ _y=T -> T; ? 9not : _x =_ _x=T -> _F; _x=F -> T; ? _2._3._4. _L_i_b_r_a_r_y _R_o_u_t_i_n_e_s sin : _x =_ _x is a number -> _s_i_n(_x); ? 9asin : _x =_ _x is a number //\_\ |_x| <_ 1 -> sin78-1999(_x); ? 9cos : _x =_ _x is a number -> _c_o_s(_x); ? 9acos : _x =_ _x is a number //\_\ |_x| <_ 1 -> cos78-1999(_x); ? 9exp : _x =_ _x is a number -> _e78_x;999 ? Berkeley FP User's Manual, Rev. 4.1 PS2:7-13 log : _x =_ _x is a positive number -> _l_n(_x); ? 9 9mod : <_x,_y> =_ _x and _y are numbers -> _x - _yx7|99|99|999_y77778_x99_|99|99|7 ; ? _2._4. _F_u_n_c_t_i_o_n_a_l _F_o_r_m_s Functional forms define new _f_u_n_c_t_i_o_n_s by operating on function and object _p_a_r_a_m_e_t_e_r_s of the form. The resultant expressions can be compared and contrasted to the _v_a_l_u_e- oriented expressions of traditional programming languages. The distinction lies in the domain of the operators; func- tional forms manipulate functions, while traditional opera- tors manipulate values. One functional form is _c_o_m_p_o_s_i_t_i_o_n. For two functions _U and _V the form _U @ _V denotes their composition _U 8o9 _V: 9 (2.4) 7 (_U @ _V) : _x =_ _U:(_V:_x), \/- _x_Z The _c_o_n_s_t_a_n_t function takes an object parameter: (2.5) 7 %_x:_y =_ _y=? -> ?; _x, \/- _x,_y _Z The function %? always returns ?. In the following description of the functional forms, we assume that _X, _X9_i8, _Y, _Y9_i8, _I, and _I9_i8 are functions and that _x, _x9_i8, _y are objects. _C_o_m_p_o_s_i_t_i_o_n (_Y @ _I):_x =_ _Y:(_I:_x) _C_o_n_s_t_r_u_c_t_i_o_n [_Y918, . . . ,_Y9_n8]:_x =_ <_Y918:_x,...,_Y9_n8:_x> Note that construction is also bottom-preserving, e.g., 9 (2.6) 7 [+,/]:<3,0> = <3,?> = ? 9 9 PS2:7-14 Berkeley FP User's Manual, Rev. 4.1 _C_o_n_d_i_t_i_o_n (_X -> _Y; _I):_x =_ 9 (_X:_x)=T -> _Y:_x; 9 (_X:_x)=F -> _I:_x; ? 9 The reader should be aware of the distinction between _f_u_n_c_t_i_o_n_a_l _e_x_p_r_e_s_s_i_o_n_s, in the variant of McCarthy's condi- tional expression, and the _f_u_n_c_t_i_o_n_a_l _f_o_r_m introduced here. In the former case the result is a _v_a_l_u_e, while in the latter case the result is a _f_u_n_c_t_i_o_n. Unlike Backus' FP, the conditional form _m_u_s_t be enclosed in parenthesis, e.g., 9 (2.7) 7 (isNegative -> - @ [%0,id] ; id) _C_o_n_s_t_a_n_t %_x:_y =_ _y=? -> ?; _x, \/- _x_Z This function returns its object parameter as its result. _R_i_g_h_t _I_n_s_e_r_t 9 !Y :_x =_ 9 _x=<> -> _e9_f8:_x; 9 _x=<_x918> -> _x918; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>2 -> _Y:<_x918, !_Y:<_x928, . . . , _x9_k8>>; ? e.g., !+:<4,5,6>=15. If _Y has a right identity element _e9_f8, then !_Y:<> = _e9_f8, e.g., 9 (2.8) 7 !+:<>=0 and !*:<>=1 Currently, identity functions are defined for + (0), - (0), * (1), / (1), also for and (T), or (F), xor (F). All other unit functions default to bottom (?). 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-15 _T_r_e_e _I_n_s_e_r_t 9 | _Y : _x =_ 9 _x=<> -> _e9_f8:_x; 9 _x=<_x918> -> _x918; 9 _x=<_x918, _x928, . . . , _x9_k8> //\_\ _k>1 -> 9 Y : <| _Y : <_x918, . . . ,_x9|_k/2|8> , | _Y : <_x9|_k/2|+18, . . . ,_x9_k8>>;? e.g., (2.9) 7 |+:<4,5,6,7> =_ +:<+:<4,5>,+:<6,7>> =_ 15 Tree insert uses the same identity functions as right insert. _A_p_p_l_y _t_o _A_l_l &_Y: _x =_ 9 _x=<> -><>; 9 _x=<_x918, _x928, . . . , _x9_k8> -> <_Y:_x918, . . . , _Y:_x9_k8>; ? _W_h_i_l_e (while _X _Y):_x =_ _X:_x=T -> (while _X _Y):(_Y:_x); 9 _X:_x=F -> _x; ? _2._5. _U_s_e_r _D_e_f_i_n_e_d _F_u_n_c_t_i_o_n_s An FP definition is entered as follows: 9 (2.10) 7 {_f_n-_n_a_m_e _f_n-_f_o_r_m}, where _f_n-_n_a_m_e is an ascii string consisting of letters, numbers and the underline symbol, and _f_n-_f_o_r_m is any valid functional form, including a single primitive or defined function. For example the function 9 PS2:7-16 Berkeley FP User's Manual, Rev. 4.1 (2.11) 7 {_f_a_c_t_o_r_i_a_l !* @ _i_o_t_a} is the non-recursive definition of the factorial func- tion. Since FP systems are applicative it is permissible to substitute the actual definition of a function for any reference to it in a functional form: if _f =_ 1@2 then _f : _x =_ 1@2 : _x, \/- _x_Z. References to undefined functions bottom out: (2.12) 7 _f:_x =_ ?\/- _x_Z, _f/F 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-17 _3. _G_e_t_t_i_n_g _o_n _a_n_d _o_f_f _t_h_e _S_y_s_t_e_m Startup FP from the shell by entering the command: /_u_s_r/_l_o_c_a_l/_f_p. The system will prompt you for input by indenting over six character positions. Exit from FP (back to the shell) with a control/D (^D). _3._1. _C_o_m_m_e_n_t_s A user may end any line (including a command) with a comment; the comment character is '#'. The interpreter will ignore any character after the '#' until it encounters a newline character or end-of-file, whichever comes first. 9 _3._2. _B_r_e_a_k_s Breaks interrupt any work in progress causing the sys- tem to do a FRANZ reset before returning control back to the user. 9 _3._3. _N_o_n-_T_e_r_m_i_n_a_t_i_o_n LISP's namestack may, on occasion, overflow. FP responds by printing "non-terminating" and returning bottom as the result of the application. It does a FRANZ reset before returning control to the user. _4. _S_y_s_t_e_m _C_o_m_m_a_n_d_s System commands start with a right parenthesis and they are followed by the command-name and possibly one or more arguments. All this information _m_u_s_t _b_e _t_y_p_e_d _o_n _a _s_i_n_g_l_e _l_i_n_e, and any number of spaces or tabs may be used to separate the components. 9 _4._1. _L_o_a_d Redirect the standard input to the file named by the command's argument. If the file doesn't exist then FP appends '.fp' to the file-name and retries the open (error if the file doesn't exist). This command allows the user to read in FP function definitions from a file. The user can also read in applications, but such operation is of little utility since none of the input is echoed at the terminal. Normally, FP returns control to the user on an end-of-file. 9 PS2:7-18 Berkeley FP User's Manual, Rev. 4.1 It will also do so whenever it does a FRANZ reset, e.g., whenever the user issues a break, or whenever the system encounters a non-terminating application. 9 _4._2. _S_a_v_e Output the source text for all user-defined functions to the file named by the argument. _4._3. _C_s_a_v_e _a_n_d _F_s_a_v_e These commands output the lisp code for all the user- defined functions, including the original source-code, to the file named by the argument. Csave pretty prints the code, Fsave does not. Unless the user wishes to examine the code, he should use 'fsave'; it is about ten times faster than 'csave', and the resulting file will be about three times smaller. These commands are intended to be used with the liszt compiler and the 'cload' command, as explained below. _4._4. _C_l_o_a_d This command loads or fasls in the file shown by the argument. First, FP appends a '.o' to the file-name, and attempts a load. Failing that, it tries to load the file named by the argument. If the user outputs his function definitions using fsave or csave, and then compiles them using liszt, then he may fasl in the compiled code and speed up the execution of his defined functions by a factor of 5 to 10. _4._5. _P_f_n Print the source text(s) (at the terminal) for the user-defined function(s) named by the argument(s) (error if the function doesn't exist). _4._6. _D_e_l_e_t_e Delete the user-defined function(s) named by the argu- ment (error if the function doesn't exist). _4._7. _F_n_s List the names of all user-defined functions in alpha- betical order. Traced functions are labeled by a trailing 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-19 '@' (see 4.7 for sample output). _4._8. _S_t_a_t_s The "stats" command has several options that help the user manage the collection of dynamic statistics for func- tions[1] and functional forms. Option names follow the key- word "stats", e.g., ")stats reset". The statistic package records the frequency of usage for each function and functional form; also the size[2] of all the arguments for all functions and functional expres- sions. These two measures allow the user to derive the average argument size per call. For functional forms the package tallies the frequency of each functional argument. Construction has an additional statistic that tells the number of functional arguments involved in the construction. Statistics are gathered whenever the mode is on, except for applications that "bottom out" (i.e., return bottom - ?). Statistic collection slows the system down by x2 to x4. The following printout illustrates the use of the statistic package (user input is emboldened): ____________________ 9 [1] Measurement of user-defined functions is done with the aid of the trace package, discussed in 4.9. [2] "Size" is the top-level length of the argument, for most functions. Exceptions are: _a_p_n_d_l, _d_i_s_t_l (top-level length of the second element), _a_p_n_d_r, _d_i_s_t_r (top-level length of the first element), and _t_r_a_n_s_p_o_s_e (top level length of each top level element). 9 PS2:7-20 Berkeley FP User's Manual, Rev. 4.1 ____________________________________________________ )stats on Stats collection turned on. +:<3 4> 7 !* @ iota :3 6 )stats print plus: times 1 times: times 2 iota: times 1 insert: times 1 size 3 Functional Args Name Times times 1 compos: times 1 size 1 Functional Args Name Times insert 1 iota 1 9 ____________________________________________________ 9 _4._8._1. _O_n Enable statistics collection. 9 _4._8._2. _O_f_f Disable statistics collection. The user may selec- tively collect statistics using the on and off commands. 9 _4._8._3. _P_r_i_n_t Print the dynamic statistics at the terminal, or, out- put them to a file. The latter option requires an addi- tional argument, e.g., ")stats print fooBar" prints the stats to the file "fooBar". Berkeley FP User's Manual, Rev. 4.1 PS2:7-21 _4._8._4. _R_e_s_e_t Reset the dynamic statistics counters. To prevent accidental loss of collected statistics, the system will query the user if he tries to reset the counters without first outputting the data (the system will also query the user if he tries to log out without outputting the data). 9 _4._9. _T_r_a_c_e Enable or disable the tracing and the dynamic measure- ment of the user defined functions named by the argument(s). The first argument tells whether to turn tracing off or on and the others give the name of the functions affected. The tracing and untracing commands are independent of the dynamic statistics commands. This command is cumulative e.g., ')trace on f1', followed by ')trace on f2' is equivalent to ')trace on f1 f2'. FP tracer output is similar to the FRANZ tracer output: function entries and exits, call level, the functional argu- ment (remember that FP functions have only one argument!), and the result, are printed at the terminal: ____________________________________________________ 9 )pfn fact {fact (eq0 -> %1 ; * @ [id, fact @ s1])} )fns eq0 fact s1 )trace on fact )fns eq0 fact@ s1 fact : 2 1 >Enter> fact [2] |2 >Enter> fact [1] | 3 >Enter> fact [0] | 3 Redirect input from save Save defined fns in pfn ... Print source text of ... delete ... Delete ... fns List all functions stats on/off/reset/print [file] Collect and print dynamic stats trace on/off ... Start/Stop exec trace of ... timer on/of Turn timer on/off script open/close/append Open or close a script-file lisp Exit to the lisp system (return with '^D') debug on/off Turn debugger output on/off csave Output Lisp code for all user-defined fns cload Load Lisp code from a file (may be compiled) fsave Same as csave except without pretty-printing _4._1_3. _S_p_e_c_i_a_l _S_y_s_t_e_m _F_u_n_c_t_i_o_n_s There are two system functions that are not generally meant to be used by average users. Berkeley FP User's Manual, Rev. 4.1 PS2:7-23 _4._1_3._1. _L_i_s_p This exits to the lisp system. Use "^D" to return to FP. _4._1_3._2. _D_e_b_u_g Turns the 'debug' flag on or off. The command ")debug on" turns the flag on, ")debug off" turns the flag off. The main purpose of the command is to print out the parse tree. 9 9 PS2:7-24 Berkeley FP User's Manual, Rev. 4.1 _5. _P_r_o_g_r_a_m_m_i_n_g _E_x_a_m_p_l_e_s We will start off by developing a larger FP program, _m_e_r_g_e_S_o_r_t. We measure _m_e_r_g_e_S_o_r_t using the trace package, and then we comment on the measurements. Following _m_e_r_- _g_e_S_o_r_t we show an actual session at the terminal. _5._1. _M_e_r_g_e_S_o_r_t The source code for _m_e_r_g_e_S_o_r_t is: 9 ____________________________________________________ 9 # Use a divide and conquer strategy {mergeSort | merge} 9 {merge atEnd @ mergeHelp @ [[], fixLists]} 9 # Must convert atomic arguments into sequences # Atomic arguments occur at the leaves of the execution tree {fixLists &(atom -> [id] ; id)} 9 # Merge until one or both input lists are empty {mergeHelp (while and @ &(not@null) @ 2 (firstIsSmaller -> takeFirst ; takeSecond))} 9 # Find the list with the smaller first element {firstIsSmaller < @ [1@1@2, 1@2@2]} 9 # Take the first element of the first list {takeFirst [apndr@[1,1@1@2], [tl@1@2, 2@2]]} 9 # Take the first element of the second list {takeSecond [apndr@[1,1@2@2], [1@2, tl@2@2]]} 9 # If one list isn't null, then append it to the # end of the merged list {atEnd (firstIsNull -> concat@[1,2@2] ; concat@[1,1@2])} 9 {firstIsNull null@1@2} 9 ____________________________________________________ 9 The merge sort algorithm uses a divide and conquer strategy; it splits the input in half, recursively sorts each half, and then merges the sorted lists. Of course, all these sub-sorts can execute in parallel, and the tree-insert (|) functional form expresses this concurrency. _M_e_r_g_e removes successively larger elements from the heads of the two lists (either _t_a_k_e_F_i_r_s_t or _t_a_k_e_S_e_c_o_n_d) and appends these elements to the end of the merged sequence. _M_e_r_g_e ter- minates when one sequence is empty, and then _a_t_E_n_d appends any remaining non-empty sequence to the end of the merged Berkeley FP User's Manual, Rev. 4.1 PS2:7-25 one. On the next page we give the trace of the function _m_e_r_g_e, which information we can use to determine the struc- ture of _m_e_r_g_e's execution tree. Since the tree is well- balanced, many of the _m_e_r_g_e's could be executed in parallel. Using this trace we can also calculate the average length of the arguments passed to _m_e_r_g_e, or a distribution of argument lengths. This information is useful for determining commun- ication costs. 9 ____________________________________________________ 9 )trace on merge mergeSort : <0 3 -2 1 11 8 -22 -33> | 3 >Enter> merge [<0 3>] | 3 | 3 >Enter> merge [<-2 1>] | 3 |2 >Enter> merge [<<0 3> <-2 1>>] |2 | 3 >Enter> merge [<11 8>] | 3 | 3 >Enter> merge [<-22 -33>] | 3 |2 >Enter> merge [<<8 11> <-33 -22>>] |2 1 >Enter> merge [<<-2 0 1 3> <-33 -22 8 11>>] 1 <-33 -22 -2 0 1 3 8 11> 9 ____________________________________________________ 9 PS2:7-26 Berkeley FP User's Manual, Rev. 4.1 _5._2. _F_P _S_e_s_s_i_o_n User input is emboldened, terminal output in Roman script. fp FP, v. 4.1 11/31/82 )load ex_man {all_le} {sort} {abs_val} {find} {ip} {mm} {eq0} {fact} {sub1} {alt_fnd} {alt_fact} )fns abs_val all_le alt_fact alt_fnd eq0 fact find ip mm sort sub1 abs_val : 3 3 abs_val : -3 3 abs_val : 0 0 abs_val : <-5 0 66> ? &abs_val : <-5 0 66> <5 0 66> )pfn abs_val {abs_val ((> @ [id,%0]) -> id ; (- @ [%0,id]))} 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-27 [id,%0] : -3 <-3 0> [%0,id] : -3 <0 -3> - @ [%0,id] : -3 3 all_le : <1 3 5 7> T all_le : <1 0 5 7> F )pfn all_le {all_le ! and @ &<= @ distl @ [1,tl]} distl @ [1,tl] : <1 2 3 4> <<1 2> <1 3> <1 4>> &<= @ distl @ [1,tl] : <1 2 3 4> ! and : F ! and : T sort : <3 1 2 4> <1 2 3 4> sort : <1> <1> sort : <> ? sort : 4 9 9 PS2:7-28 Berkeley FP User's Manual, Rev. 4.1 ? )pfn sort {sort (null @ tl -> [1] ; (all_le -> apndl @ [1,sort@tl]; sort@rotl))} fact : 3 6 )pfn fact sub1 eq0 {fact (eq0 -> %1 ; *@[id , fact@sub1])} {sub1 -@[id,%1]} {eq0 = @ [id,%0]} &fact : <1 2 3 4 5> <1 2 6 24 120> eq0 : 3 F eq0 : <> F eq0 : 0 T sub1 : 3 2 %1 : 3 1 alt_fact : 3 6 )pfn alt_fact {alt_fact !* @ iota} iota : 3 <1 2 3> 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-29 !* @ iota : 3 6 !+ : <1 2 3> 6 find : <3 <3 4 5>> T find : <<> <3 4 <>>> T find : <3 <4 5>> F )pfn find {find (null@2 -> %F ; (=@[1,1@2] -> %T ; find@[1,tl@2]))} [1,tl@2] : <3 <3 4 5>> <3 <4 5>> [1,1@2] : <3 <3 4 5>> <3 3> alt_fnd : <3 <3 4 5>> T )pfn alt_fnd {alt_fnd ! or @ &eq @ distl } distl : <3 <3 4 5>> <<3 3> <3 4> <3 5>> &eq @ distl : <3 <3 4 5>> !or : T !or : 9 9 PS2:7-30 Berkeley FP User's Manual, Rev. 4.1 F )delete alt_fnd )fns abs_val all_le alt_fact eq0 fact find ip mm sort sub1 alt_fnd : <3 <3 4 5>> alt_fnd not defined ? {g g} {g} g : 3 non-terminating ? [Return to top level] FP, v. 4.0 10/8/82 [+,*] : <3 4> <7 12> [+,* : <3 4> syntax error: [+,* : <3 4> ^ ip : <<3 4 5> <5 6 7>> 74 )pfn ip {ip !+ @ &* @ trans} trans : <<3 4 5> <5 6 7>> <<3 5> <4 6> <5 7>> &* @ trans : <<3 4 5> <5 6 7>> Berkeley FP User's Manual, Rev. 4.1 PS2:7-31 <15 24 35> mm : <<<1 0> <0 1>> <<3 4> <5 6>>> <<3 4> <5 6>> )pfn mm {mm &&ip @ &distl @ distr @[1,trans@2]} [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>> <<<1 0> <0 1>> <<3 4> <5 6>>> distr : <<<1 0> <0 1>> <<3 4> <5 6>>> <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>> &distl : <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>> <<<<1 0> <3 4>> <<1 0> <5 6>>> <<<0 1> <3 4>> <<0 1> <5 6>>>> &ip @ &dist & distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>> syntax error: [+,* : <3 4> ^ &ip @ &distl & distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>> ^ &ip @ &distl @ distr @ [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>> ? 9 9 PS2:7-32 Berkeley FP User's Manual, Rev. 4.1 _6. _I_m_p_l_e_m_e_n_t_a_t_i_o_n _N_o_t_e_s FP was written in 3000 lines of FRANZ LISP [Fod 80]. Table 1 breaks down the distribution of the code by func- tionality. 8 ____________________________ Functionality % (bytes) 8 ________________________________________________________ compiler 34 user interface 32 dynamic stats 16 primitives 14 miscellaneous 3 8 ____________________________ 7 |7|7|7|7|7|7| |7|7|7|7|7|7| |7|7|7|7|7|7| 9 _T_a_b_l_e _1 9 _6._1. _T_h_e _T_o_p _L_e_v_e_l The top-level function _r_u_n_F_p starts up the subsystem by calling the routine _f_p_M_a_i_n, that takes three arguments: 9 (1) A boolean argument that says whether debugging output will be enabled. (2) A Font identifier. Currently the only one is supported 'asc (ASCII). (3) A boolean argument that identifies whether the interpreter was invoked from the shell. If so then all exits from FP return the user back to the shell. The compiler converts the FP functions into LISP equivalents in two stages: first it forms the parse tree, and then it does the code generation. _6._2. _T_h_e _S_c_a_n_n_e_r The scanner consists of a main routine, _g_e_t__t_k_n, and a set of action functions. There exists one set of action functions for each character font (currently only ASCII is supported). All the action functions are named _s_c_a_n$<_f_o_n_t>, where <_f_o_n_t> is the specified font, and each is keyed on a Berkeley FP User's Manual, Rev. 4.1 PS2:7-33 particular character (or sometimes a particular character- type - e.g., a letter or a number). _g_e_t__t_k_n returns the token type, and any ancillary information, e.g., for the token "name" the name itself will also be provided. (See Appendix C for the font-token name correspondences). When a character has been read the scanner finds the action func- tion by doing a (_g_e_t '_s_c_a_n$ <_f_o_n_t> <_c_h_a_r>) A syntax error message will be generated if no action exists for the particular character read. _6._3. _T_h_e _P_a_r_s_e_r The main parsing function, _p_a_r_s_e, accepts a single argument, that identifies the parsing context, or type of construct being handled. Table 2 shows the valid parsing contexts. 8 _______________________________ id construct 8 ______________________________________________________________ top_lev initial call constr$$ construction compos$$ composition alpha$$ apply-to-all insert$$ insert ti$$ tree insert arrow$$ 7 affirmative clause of conditional semi$$ 7 negative clause of conditional lparen$$ parenthetic expr. while$$ while 8 _______________________________ 7 |7|7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7|7| _T_a_b_l_e _2, _V_a_l_i_d _P_a_r_s_i_n_g _C_o_n_t_e_x_t_s For each type of token there exists a set of parse action functions, of the name _p$<_t_k_n-_n_a_m_e>. Each parse- action function is keyed on a valid context, and it is looked up in the same manner as scan action functions are looked up. If an action function cannot be found, then there is a syntax error in the source code. Parsing proceeds as follows: initially _p_a_r_s_e is called from the top-level, with the context argument set to "_t_o_p__l_e_v". Cer- tain tokens cause parse to be recursively invoked using that 9 PS2:7-34 Berkeley FP User's Manual, Rev. 4.1 token as a context. The result is the parse tree. _6._4. _T_h_e _C_o_d_e _G_e_n_e_r_a_t_o_r The system compiles FP source into LISP source. Nor- mally, this code is interpreted by the FRANZ LISP system. To speed up the implementation, there is an option to com- pile into machine code using the _l_i_s_z_t compiler [Joy 79]. This feature improves performance tenfold, for some pro- grams. The compiler expands all functional forms into their LISP equivalents instead of inserting calls to functions that generate the code at run-time. Otherwise, _l_i_s_z_t would be ineffective in speeding up execution since all the func- tional forms would be executed interpretively. Although the amount of code generated by an expanding compiler is 3 or 4 times greater than would be generated by a non-expanding compiler, even in interpreted mode the code runs twice as quickly as unexpanded code. With _l_i_s_z_t compilation this performance advantage increases to more than tenfold. A parse tree is either an atom or a hunk of parse trees. An atomic parse-tree identifies either an fp built- in function or a user defined function. The hunk-type parse tree represents functional forms, e.g., compose or con- struct. The first element identifies the functional form and the other elements are its functional parameters (they may in turn be functional forms). Table 3 shows the parse-tree formats. 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-35 8 ______________________________________________________ Form Format 8 ____________________________________________________________________________________________________________ user-defined fp builtin apply-to-all {_a_l_p_h_a$$ _F} insert {_i_n_s_e_r_t$$ _F} tree insert {_t_i$$ _F} select {_s_e_l_e_c_t$$ _M} constant {_c_o_n_s_t_a_n_t$$ _M} conditional {_c_o_n_d_i_t$$ _F918 _F928 _F938} while {_w_h_i_l_e$$ _F918 _F928} compose {_c_o_m_p_o_s$$ _F918 _F928} construct {_c_o_n_s_t_r$$ _F918 _F928 , . . . , _F9_n8 _n_i_l} 8 ______________________________________________________ 7 |7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7| Note: _F and the _F9_k8 are parse-trees and _M is an optional- ly signed integer constant. _T_a_b_l_e _3, _P_a_r_s_e-_T_r_e_e _F_o_r_m_a_t_s _6._5. _F_u_n_c_t_i_o_n _D_e_f_i_n_i_t_i_o_n _a_n_d _A_p_p_l_i_c_a_t_i_o_n Once the code has been generated, then the system defines the function via _p_u_t_d. The source code is placed onto a property list, '_s_o_u_r_c_e_s, to permit later access by the system commands. For an application, the indicated function is compiled and then defined, only temporarily, as _t_m_p$$. The single argument is read and _t_m_p$$ is applied to it. _6._6. _F_u_n_c_t_i_o_n _N_a_m_i_n_g _C_o_n_v_e_n_t_i_o_n_s When the parser detects a named primitive function, it returns the name <_n_a_m_e>$_f_p, where <_n_a_m_e> is the name that was parsed (all primitive function-names end in $_f_p). See Appendix D for the symbolic (e.g., compose, +) function names. Any name that isn't found in the list of builtin func- tions is assumed to represent a user-defined function; hence, it isn't possible to redefine FP primitive functions. FP protects itself from accidental or malicious internal destruction by appending the suffix "__f_p" to all user- defined function names, before they are defined. 9 PS2:7-36 Berkeley FP User's Manual, Rev. 4.1 _6._7. _M_e_a_s_u_r_e_m_e_n_t _I_m_p_e_l_e_m_e_n_t_a_t_i_o_n This work was done by Dorab Patel at UCLA. Most of the measurement code is in the file 'fpMeasures.l'. Many of the remaining changes were effected in 'primFp.l', to add calls on the measurement package at run-time; to 'codeGen.l', to add tracing of user defined functions; to 'utils.l', to add the new system commands; and to 'fpMain.l', to protect the user from forgetting to output statistics when he leaves FP. _6._7._1. _D_a_t_a _S_t_r_u_c_t_u_r_e_s All the statistics are in the property list of the glo- bal symbol _M_e_a_s_u_r_e_s. Associated with each each function (primitive or user-defined, or functional form) is an indi- cator; the statistics gathered for each function are the corresponding values. The names corresponding to primitive functions and functional forms end in '$fp' and the names corresponding to user-defined functions end in '_fp'. Each of the property values is an association list: (get 'Measures 'rotl$fp) ==> ((times . 0) (size . 0)) The car of the pair is the name of the statistic (i.e., times, size) and the cdr is the value. There is one excep- tion. Functional forms have a statistic called funargtyp. Instead of being a dotted pair, it is a list of two ele- ments: (get 'Measures 'compose$fp) ==> ((times . 2) (size . 4) (funargtyp ((select$fp . 2) (sub$fp . 2)))) The car is the atom 'funargtyp' and the cdr is an alist. Each element of the alist consists of a functional argument-frequency dotted pair. The statistic packages uses two other global symbols. The symbol DynTraceFlg is non-nil if dynamic statistics are being collected and is nil otherwise. The symbol TracedFns is a list (initially nil) of the names of the user functions being traced. _6._7._2. _I_n_t_e_r_p_r_e_t_a_t_i_o_n _o_f _D_a_t_a _S_t_r_u_c_t_u_r_e_s _6._7._2._1. _T_i_m_e_s The number of times this function has been called. All functions and functional forms have this statistic. Berkeley FP User's Manual, Rev. 4.1 PS2:7-37 _6._7._2._2. _S_i_z_e The sum of the sizes of the arguments passed to this function. This could be divided by the times statistic to give the average size of argument this function was passed. With few exceptions, the size of an object is its top-level length (note: version 4.0 defined the size as the total number of _a_t_o_m_s in the object); the empty sequence, "<>", has a size of 0 and all other atoms have size of one. The exceptions are: _a_p_n_d_l, _d_i_s_t_l (top-level length of the second element), _a_p_n_d_r, _d_i_s_t_r (top-level length of the first ele- ment), and _t_r_a_n_s_p_o_s_e (top level length of each top level element). This statistic is not collected for some primitive functions (mainly binary operators like +,-,*). _6._7._2._3. _F_u_n_a_r_g_n_o The number of functional arguments supplied to a func- tional form. Currently this statistic is gatherered only for the construction functional form. _6._7._2._4. _F_u_n_a_r_g_t_y_p How many times the named function was used as a func- tional parameter to the particular functional form. _6._8. _T_r_a_c_e _I_n_f_o_r_m_a_t_i_o_n The level number of a call shows the number of steps required to execute the function on an ideal machine (i.e., one with unbounded resources). The level number is calcu- lated under an assumption of infinite resources, and the system evaluates the condition of a conditional before evaluating either of its clauses. The number of functions executed at each level can give an idea of the distribution of parallelism in the given FP program. _7. _A_c_k_n_o_w_l_e_d_g_e_m_e_n_t_s Steve Muchnick proposed the initial construction of this system. Bob Ballance added some of is own insights, and John Foderaro provided helpful hints regarding effective use of the FRANZ LISP system [Fod80]. Dorab Patel [Pat81] wrote the dynamic trace and statistics package and made gen- eral improvements to the user interface. Portions of this manual were excerpted from the _C_O_M_P_C_O_N-_8_3 _D_i_g_e_s_t _o_f 9 9 PS2:7-38 Berkeley FP User's Manual, Rev. 4.1 _P_a_p_e_r_s[3]. _8. _R_e_f_e_r_e_n_c_e_s [Bac78] John Backus, "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs," _C_A_C_M, Turing Award Lecture, 21, 8 (August 1978), 613-641. 9 [Fod80] John K. Foderaro, "The FRANZ LISP Manual," University of California, Berkeley, California, 1980. 9 [Joy79] W.N. Joy, O. Babaoglu, "UNIX Programmer's Manual," November 7, 1979, Computer Science Division, University of California, Berkeley, California. 9 [Mc60] J. McCarthy, "Recursive Functions of Symbolic expressions and their Computation by Machine," Part I, _C_A_C_M 3, 4 (April 1960), 184-195. 9 [Pat80] Dorab Ratan Patel, "A System Organization for Applicative Programming," M.S Thesis, University of California, Los Angeles, California, 1980. 9 [Pat81] Dorab Patel, "Functional Language Interpreter User Manual," University of California, Los Angeles, Califor- nia, 1981. 9____________________ 9 [3] Scott B. Baden and Dorab R. Patel, "Berkeley FP - Ex- periences With a Functional Programming Language", 8c9 1982, IEEE. 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-39 _A_p_p_e_n_d_i_x _A: _L_o_c_a_l _M_o_d_i_f_i_c_a_t_i_o_n_s _1. _C_h_a_r_a_c_t_e_r _S_e_t _C_h_a_n_g_e_s Backus [Ba78] used some characters that do not appear on our ASCII terminals, so we have made the following sub- stitutions: 8 ________________________ constant _x8_9 %_x insert / ! apply-to-all A & composition 8o9 @ arrow -> -> empty set U <> bottom _| ? divide / / multiply x * 8 ________________________ 7 |8|7|7|7|7|7|7|7|7| 9 |8|7|7|7|7|7|7|7|7| 9 |8|7|7|7|7|7|7|7|7| 9 |8|7|7|7|7|7|7|7|7| 9 _2. _S_y_n_t_a_c_t_i_c _M_o_d_i_f_i_c_a_t_i_o_n_s _2._1. _W_h_i_l_e _a_n_d _C_o_n_d_i_t_i_o_n_a_l While and conditional functional expressions _m_u_s_t be enclosed in parenthesis, e.g., (while _f _g) (_p -> _f ; _g) _2._2. _F_u_n_c_t_i_o_n _D_e_f_i_n_i_t_i_o_n_s Function definitions are enclosed by curly braces; they consist of a name-definition pair, separated by blanks. For example: {_f_a_c_t !* @ iota} defines the function fact (the reader should recognize this as the non-recursive factorial function). 9 9 PS2:7-40 Berkeley FP User's Manual, Rev. 4.1 _2._3. _S_e_q_u_e_n_c_e _C_o_n_s_t_r_u_c_t_i_o_n It is not necessary to separate elements of a sequences with a comma; a blank will suffice: <1,2,3> =_ <1 2 3> For nested sequences, the terminating right angle bracket acts as the delimiter: <<1,2,3>,<4,5,6>> =_ <<1 2 3><4 5 6>> _3. _U_s_e_r _I_n_t_e_r_f_a_c_e We have provided a rich set of commands that allow the user to catalog, print, and delete functions, to load them from a file and to save them away. The user may generate script files, dynamically trace and measure functional expression execution, generate debugging output, and, tem- porarily exit to the FRANZ LISP system. A command must begin with a right parenthesis. Consult Appendix C for a complete description of the command syntax. Debugging in FP is difficult; all undefined results map to a single atom - _b_o_t_t_o_m ("?"). To pinpoint the cause of an error the user can use the special debugging output func- tion, out, or the tracer. _4. _A_d_d_i_t_i_o_n_s _a_n_d _O_m_m_i_s_s_i_o_n_s Many relational functions have been added: <, >, =, =/, <_, >_; their syntax is: <, >, =, ~=, <=, >=. Also added are the iota function (This is the APL iota func- tion an n-element sequence of natural numbers) and the exclusive OR (O+) function. Several new structural functions have been added: pair pairs up successive elements of a sequence, split splits a sequence into two (roughly) equal halves, last returns the last element of the sequence (<> if the sequence is empty), first returns the first element of the sequence (<> if it is empty), and concat concatenates all subsequences of a sequence, squeezing out null sequences (<>). Front is equivalent to tlr. Pick is a parameterized form of the selector function; the first component of the argument selects a single element from the second component. Out is the only side-effect function; it is equivalent to the id Berkeley FP User's Manual, Rev. 4.1 PS2:7-41 function but it also prints its argument out at the termi- nal. This function is intended to be used only for debug- ging. One new functional form has been added, tree insert. This functional form breaks up the the argument into two roughly equal pieces applying itself recursively to the two halves. The functional parameter is applied to the result. The binary-to-unary functions ('bu') has been omitted. Seven mathematical library functions have been added: sin, cos, asin (sin78-1999), acos (cos78-1999), log, exp, and mod (the remainder function) 9 9 PS2:7-42 Berkeley FP User's Manual, Rev. 4.1 _A_p_p_e_n_d_i_x _B: _F_P _G_r_a_m_m_a_r _I. _B_N_F _S_y_n_t_a_x fpInput -> (fnDef | application | fpCmda)* | '^D' fnDef -> '{' name funForm '}' application -> funForm ':' object name -> letter (letter | digit | '_')* nameList -> (name)* object -> atom | fpSequence | '?' fpSequence -> '<' (S | object ((',' | ' ') object)*) '>' atom -> 'T' | 'F' | '<>' | '"' (ascii-char)* '"' | (letter | digit)* | number funForm -> simpFn | composition | construction | conditional | constantFn | insertion | alpha | while | '(' funForm ')' simpFn -> fpDefined | fpBuiltin fpDefined -> name fpBuiltin -> selectFn | 'tl' | 'id' | 'atom' | 'not' | 'eq' | relFn | 'null' | 'reverse' | 'distl' | 'distr' | 'length' | binaryFn | 'trans' | 'apndl' | 'apndr' | 'tlr' | 'rotl' | 'rotr' | 'iota' | 'pair' | 'split' | 'concat' | 'last' | 'libFn' selectFn -> (S | '+' | '-') unsignedInteger relFn -> '<=' | '<' | '=' | '~=' | '>' | '>=' binaryFn -> '+' | '-' | '*' | '/' | 'or' | 'and' | 'xor' libFn -> 'sin' | 'cos' | 'asin' | 'acos' | 'log' | 'exp' | 'mod' composition -> funForm '@' funForm construction -> '[' formList ']' 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-43 formList -> S | funForm (',' funForm)* conditional -> '(' funForm '->' funForm ';' funForm ')' constantFn -> '%' object insertion -> '!' funForm | '|' funForm alpha -> '&' funForm while -> '(' 'while' funForm funForm ')' _I_I. _P_r_e_c_e_d_e_n_c_e_s 1. %, !, & (highest) 2. @ 3. [ . . . ] 4. -> . . . ; . . . 5. while (least) a Command Syntax is listed in Appendix C. 9 9 PS2:7-44 Berkeley FP User's Manual, Rev. 4.1 _A_p_p_e_n_d_i_x _C: _C_o_m_m_a_n_d _S_y_n_t_a_x All commands begin with a right parenthesis (")"). )fns )pfn )load )cload )save )csave )fsave )delete )stats on )stats off )stats reset )stats print [UNIX file name] )trace on )trace off )timer on )timer off )debug on )debug off )script open )script close )script append )help )lisp 9 9 Berkeley FP User's Manual, Rev. 4.1 PS2:7-45 _A_p_p_e_n_d_i_x _D: _T_o_k_e_n-_N_a_m_e _C_o_r_r_e_s_p_o_n_d_e_n_c_e_s 8 ____________________ Token Name 8 ________________________________________ [ lbrack$$ ] rbrack$$ { lbrace$$ } rbrace$$ ( lparen$$ ) rparen$$ @ compos$$ ! insert$$ | ti$$ & alpha$$ ; semi$$ : colon$$ , comma$$ + builtin$$ + _M78_a999 select$$ * builtin$$ / builtin$$ = builtin$$ - builtin$$ -> arrow$$ - _M select$$ > builtin$$ >= builtin$$ < builtin$$ <= builtin$$ ~= builtin$$ %_o78_b999 constant$$ 8 ____________________ 7 |7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7|7| a M is an optionally signed integer constant. b o is any FP object. 9 PS2:7-46 Berkeley FP User's Manual, Rev. 4.1 _A_p_p_e_n_d_i_x _E: _S_y_m_b_o_l_i_c _P_r_i_m_i_t_i_v_e _F_u_n_c_t_i_o_n _N_a_m_e_s The scanner assigns names to the alphabetic primitive functions by appending the string "$fp" to the end of the function name. The following table designates the naming assignments to the non-alphabetic primitive function names. 8 _____________________ Function Name 8 __________________________________________ + plus$fp - minus$fp * times$fp / div$fp = eq$fp > gt$fp >= ge$fp < lt$fp <= le$fp ~= ne$fp 8 _____________________ 7 |7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7| |7|7|7|7|7|7|7|7|7|7|7| 9 PS2:7-2 Berkeley FP User's Manual, Rev. 4.1 _T_a_b_l_e _o_f _C_o_n_t_e_n_t_s 1. Background ........................................ 4 2. System Description ................................ 7 2.1. Objects ......................................... 7 2.2. Application ..................................... 7 2.3. Functions ....................................... 8 2.3.1. Structural .................................... 8 2.3.2. Predicate (Test) Functions .................... 12 2.3.3. Arithmetic/Logical ............................ 12 2.3.4. Library Routines .............................. 12 2.4. Functional Forms ................................ 13 2.5. User Defined Functions .......................... 15 3. Getting on and off the System ..................... 17 3.1. Comments ........................................ 17 3.2. Breaks .......................................... 17 3.3. Non-Termination ................................. 17 4. System Commands ................................... 17 4.1. Load ............................................ 17 4.2. Save ............................................ 18 4.3. Csave and Fsave ................................. 18 4.4. Cload ........................................... 18 4.5. Pfn ............................................. 18 4.6. Delete .......................................... 18 4.7. Fns ............................................. 18 4.8. Stats ........................................... 19 4.8.1. On ............................................ 20 4.8.2. Off ........................................... 20 4.8.3. Print ......................................... 20 4.8.4. Reset ......................................... 21 4.9. Trace ........................................... 21 4.10. Timer .......................................... 22 4.11. Script ......................................... 22 4.12. Help ........................................... 22 4.13. Special System Functions ....................... 22 4.13.1. Lisp ......................................... 23 4.13.2. Debug ........................................ 23 5. Programming Examples .............................. 24 5.1. MergeSort ....................................... 24 5.2. FP Session ...................................... 26 6. Implementation Notes .............................. 32 6.1. The Top Level ................................... 32 6.2. The Scanner ..................................... 32 6.3. The Parser ...................................... 33 6.4. The Code Generator .............................. 34 6.5. Function Definition and Application ............. 35 6.6. Function Naming Conventions ..................... 35 6.7. Measurement Impelementation ..................... 36 6.7.1. Data Structures ............................... 36 6.7.2. Interpretation of Data Structures ............. 36 6.7.2.1. Times ....................................... 36 6.7.2.2. Size ........................................ 37 6.7.2.3. Funargno .................................... 37 Berkeley FP User's Manual, Rev. 4.1 PS2:7-3 6.7.2.4. Funargtyp ................................... 37 6.8. Trace Information ............................... 37 7. Acknowledgements .................................. 37 8. References ........................................ 38 Appendix A: Local Modifications ..................... 39 1. Character Set Changes ............................. 39 2. Syntactic Modifications ........................... 39 2.1. While and Conditional ........................... 39 2.2. Function Definitions ............................ 39 2.3. Sequence Construction ........................... 40 3. User Interface .................................... 40 4. Additions and Ommissions .......................... 40 Appendix B: FP Grammar .............................. 42 Appendix C: Command Syntax .......................... 44 Appendix D: Token-Name Correspondences .............. 45 Appendix E: Symbolic Primitive Function Names ....... 46 9 9 PS2:7-4 Berkeley FP User's Manual, Rev. 4.1 9 9