IFP Reference 1 _1. _B_u_i_l_t-_i_n _F_u_n_c_t_i_o_n_s This section is a reference guide to the built-in functions in IFP. The following sets (types) are used in the definitions of functions: A atoms B boolean values O objects R real numbers Z integers S strings T* sequences with element type T T+ non-empty sequences with element type T Tn sequences of length n with element type T A function returns ``?'' if the argument is not in its domain. The notation xn denotes the nth element of a sequence X. For example, the domain of the addition function is [X,Y] in [R,R]. That is addition takes a pair of real numbers as its argument. We could also write this as [X,Y] in R2, since a pair is a sequence of length two. December 5, 1985 IFP Reference 2 _1._1. _S_t_r_u_c_t_u_r_a_l _F_u_n_c_t_i_o_n_s (/_s_y_s) Structural functions are assemble, reorganize, and select data. The primitive structural functions are listed below: ______________________________________________________________________ _|N_a_m_e_______D_o_m_a_i_n__________________D_e_f_i_n_i_t_i_o_n___________________________| | | |apndl [X,Y] in [O,On] | | | |apndr [X,Y] in [Om,O] | | | |cat X in O** catenate sequences | | | |distl [X,Y] in [O,On] < ... > | | | |distr [X,Y] in [Om,O] < ... > | | | |dropl [X,K] in [On, 0<_Z<_n] drop K elements from left end of X | | | |dropr [X,K] in [On, 0<_Z<_n] drop K elements from right end of X| | | |iota n in Z>_0 <1,2,...n> | | | |length X in On number of elements in X | | | |pick [X,K] in [On, 0 of length K | | | |reverse X in On reversal of X | | | |takel [X,K] in [On, 0<_Z<_n] take K elements from left end of X | | | |taker [X,K] in [On, 0<_Z<_n] take K elements from right end of X| | | |tl X in O+ (tail) drop first element of X | | | |tlr X in O+ (right tail) drop last element of X| | | |trans X is matrix transpose X | _|_____________________________________________________________________| December 5, 1985 IFP Reference 3 _1._2. _A_r_i_t_h_m_e_t_i_c (/_m_a_t_h/_a_r_i_t_h) Most IFP arithmetic functions are found here. Below is a table of the existing functions. Some function's domain may be further restricted due to range limitations. ____________________________________________________ |_N_a_m_e______D_o_m_a_i_n______________D_e_f_i_n_i_t_i_o_n______________| | | | + [X,Y] in [R,R] X+Y | | | | - ... X-Y | | | | * ... XxY | | | | % [X,Y] in [R,R=/0] X/Y | | | | add1 X in R X+1 | | | | arcsin X in R, -1<_X<_1 arcsine X | | | | arccos X in R, -1<_X<_1 arccosine X | | | | arctan X in R arctangent X | | | | cos X in R cosine X | | | | div [X,Y] in [R,R=/0] floor (X/Y) | | | | exp X in R e to the Xth power | | | | ln X in R>0 natural logarithm of X| | | | max [X,Y] in [R,R] maximum of X and Y | | | | min [X,Y] in [R,R] minimum of X and Y | | | | minus X in R -X | | | | mod [X,Y] in [R,R] X modulo Y | | | | power [X,Y] in [R>_0,R] X to Yth power | | | | sin X in R sine X | | | | sqrt X in R>0 square root of X | | | | sub1 X in R X-1 | | | | sum X in R* summation of X | | | | tan X in R tangent of X | |____________________________________________________| December 5, 1985 IFP Reference 4 _1._3. _L_o_g_i_c (/_m_a_t_h/_l_o_g_i_c) Most IFP primitive functions returning boolean values are found here. Below is a table of the existing functions: ______________________________________________________________________ _|N_a_m_e_______D_o_m_a_i_n____________________D_e_f_i_n_i_t_i_o_n_________________________| | | |= [X,Y] in [O,O] X=Y | | | |~= ... X=/Y | | | |< [X,Y] in [R,R] u [S,S] X= ... X>_Y | | | |> ... X>Y | | | |~ X in B not X | | | |and [X,Y] in [B,B] X AND Y | | | |all X in B* all elements of X are true | | | |any X in B* at least one element of X is true| | | |atom X in O X is an atom | | | |boolean X in O X is boolean | | | |false X in O X is #f | | | |imply [X,Y] in [B,B] ~X OR Y | | | |longer [X,Y] in [Om,On] m>n | | | |member [X,Y] in [O*,O] Y is an element of X | | | |numeric X in O X is a number | | | |null X in O* X = <> | | | |odd X in Z X is odd | | | |or [X,Y] in [B,B] X OR Y | | | |pair X in O X is a pair | | | |shorter [X,Y] in [Om, On] m > : apply -> 7 _________________________________________________________________ assoc [X,Y] in [(O+)*,O] associative lookup X is an association sequence, which is a sequence of non-empty subsequences. The first element of each subse- quence is the _k_e_y of the subsequence. The result of as- soc is the first subsequence of X with a key equal to Y. If no matching key is found, f is returned. The key may be any type of object. Examples: << > w> -> << > U> -> f _________________________________________________________________ December 5, 1985 IFP Reference 6 def X in S+ definition The definition function returns the object representation of its argument. The representation of a function is a sequence of strings denoting its absolute path. The representation of a PFO is a sequence. The first element of the sequence is a path to the PFO. The remaining ele- ments of the sequence are parameters of the functional form. Suppose, for example, we define the inner product function: DEF Inner AS trans | EACH * END | INSERT + END and ``Inner'' is defined with a module with path ``/math/linear''. Then `` : def'' will result in: < < > < > > Currently, the representations of PFO are: #c < #c> #? <> n < n> nr < n> f1 | f2 | ... fn <, f1 , f2 , ... fn> [f1 , f2 , ... fn ] <, f1 , f2 , ... fn> ^c < c> EACH f END < f> FILTER p END < p> INSERT f END < f> IF p THEN g ELSE h END < p g h> WHILE p DO f END < p f> ELSIF clauses are always expanded into equivalent nested IF- THEN-ELSE constructions. Note the special case for #?, the representation < ?> would be useless due to the bottom-preserving property. _________________________________________________________________ id X in O identity The identity function returns its argument. It is useful as a place holder in PFO. For example, the ``square'' function can be written as: DEF Square AS [id,id] | *; December 5, 1985 IFP Reference 7 _2. _P_r_o_g_r_a_m _F_o_r_m_i_n_g _O_p_e_r_a_t_i_o_n_s Program forming operations combine functions and objects to create new functions. _2._1. _C_o_n_s_t_a_n_t Constant functions always return the same result when applied to any value which is not ``?''. Constant functions are written as: #c where c is the constant value to be returned. A constant function applied to ``?'' results in ``?''. Note that the function ``#?'' always returns `?'. Examples: 923 : # -> : #427 -> 427 ? : # -> ? 5 : #? -> ? _2._2. _S_e_l_e_c_t_i_o_n Selector functions return the nth element of a sequence and are written as n, where n is a positive integer. Note the dis- tinction between #5, which returns the value 5, and 5, which returns the fifth element of its argument. There are also a corresponding set of select-from-right functions, written as nr. These select the nth element of a sequence, counting from the right. All selectors return ``?'' if the argument has no nth ele- ment or is not a sequence. Below are some examples of applying selector functions: : 1 -> a : 2 -> b : 1r -> cherry : 4 -> ? December 5, 1985 IFP Reference 8 hello : 1 -> ? _2._3. _C_o_m_p_o_s_i_t_i_o_n The function composition of two functions is written as: f | g Applying the result function is the same as applying f and then g. E.g.: Function composition is defined by the equality: x : (f | g) =_ (x : f) : g Since function composition is associative, the composition of more than two functions does not require parentheses. The compo- sition of f1,f2,...fn is written: f1 | f2 | ...fn Composition syntax is identical to UNIX's pipe notation for a reason: function composition is isomorphic to a pipe between processes without side effects. _2._4. _C_o_n_s_t_r_u_c_t_i_o_n The construction of functions is written as bracketed list of the functions. For example, the construction of functions fi is written: [f1,f2,...fn] Function construction is defined by the equality: x : [f1,f2,...fn] =_ _2._5. _A_p_p_l_y _t_o _E_a_c_h The EACH functional form applys a function to each element of a sequence. It is written as December 5, 1985 IFP Reference 9 EACH f END It is defined by the equality: : EACH f END =_ _2._6. _I_f-_T_h_e_n-_E_l_s_e The IF functional form allows conditional function applica- tion. It is written as IF p THEN g ELSE h END and is defined by the equality: | x:g if p=#t | x : IF p THEN g ELSE h END =_ | x:h if p=#f | ? otherwise | The level of nesting of conditional forms may be reduced by using ELSIF clauses: IF p1 THEN f1 ELSIF p2 THEN f2 ELSIF ... ELSE g END _2._7. _F_i_l_t_e_r The FILTER functional form filters through elements of a sequence satisfying a predicate. It is written as: FILTER p END where p is the predicate. It is defined by the functional equal- ity: FILTER p END =_ EACH IF p THEN [id] ELSE [ ] END END | cat For example, if you wish to find all numeric elements in a sequence, you could write: December 5, 1985 IFP Reference 10 FILTER numeric END The FILTER functional form is an IFP extension to Backus' FP. _2._8. _R_i_g_h_t _I_n_s_e_r_t The INSERT functional form is defined by the recursion: INSERT f END =_ IF tl|null THEN 1 ELSE [1,tl | INSERT f END] | f END Typically it is used for crunching a sequence down. For example, INSERT + END returns the sum of a sequence. Unlike Backus' FP, functions formed with INSERT are always undefined for empty sequences. The reason is that it is imprac- tical for the interpreter to know the identity element of user- defined functions. The number of cases where the interpreter could know the identity element are so few that you might as well define special functions for those cases, e.g: DEF sum AS IF null THEN #0 ELSE INSERT + END END; Alternatively, you can append the identity element to the end of the sequence before inserting, e.g.: DEF sum AS [id,#0] | apndr | INSERT + END; Currently there is no ``left insert'' form.d The left insertion of f can be written as: reverse | INSERT reverse|f END December 5, 1985 IFP Reference 11 _2._9. _W_h_i_l_e The WHILE functional form allows indefinite composition. It is written as: WHILE p DO f END; and is defined by the recursive functional equality: WHILE p DO f END =_ IF p THEN f | WHILE p DO f END ELSE id END _2._1_0. _F_e_t_c_h The fetch functional form allows easy access to association sequences (see function /sys/assoc for a description of associa- tion sequences.) A fetch is written as ^c, where c is an object. The fetch form is defined by the functional equality: ^c =_ IF EACH pair END | all THEN [id,#c]|assoc|2 ELSE #? END; Note that the input is restricted to a sequence of pairs. _3. _C_o_m_m_e_n_t_s Comments are delimited by matching pairs of ``(*'' and ``*)''. Comments may be inserted anywhere not adjacent to a token. For example: DEF foo AS bar; (* This is a comment. DEF foo AS bar is not a comment *) _4. _S_y_n_t_a_x _S_u_m_m_a_r_y Below is an EBNF grammar for IFP: December 5, 1985 IFP Reference 12 ____________________________________________________________________________ |Def -> 'DEF String 'AS' Comp ';' | |Comp -> Simple { '|' Simple } | |Simple -> Conditional | Constant | Construction | Each | Filter || | Insert | Path | While | Fetch | Debug | |Conditional -> 'IF' Comp 'THEN' Comp { 'ELSIF' Comp 'THEN' Comp } | | 'ELSE' Comp 'END' | |While -> 'WHILE' Comp 'DO' Comp 'end' | |Insert -> 'INSERT' Comp 'END' | |Each -> 'EACH' Comp 'END' | |Filter -> 'FILTER' Comp 'END' | |Fetch -> '^' String | |Constant -> '#' Object | |Debug -> '@' Object | |Construction -> '[' [Comp {',' Comp}] ']' | |Path -> ['/'] String {'/' String} | |Object -> Bottom | Atom | '<' [Atom {','Atom}] '>' | |Bottom -> '?' | |Atom -> Number | String | Boolean | _||B_o_o_l_e_a_n__-_>_________'_t_'__|__'_f_'_________________________________________________|| Strings may be in single or double quotes. The strings ``t'' and ``f'' must be quoted to distinguish them from boolean atoms. Strings of digits must also be quoted to distinguish them from numeric atoms. _5. _R_u_n_n_i_n_g _I_F_P _w_i_t_h _M_S-_D_O_S _5._1. _P_r_e_r_e_q_u_i_s_i_t_e _H_a_r_d_w_a_r_e The MS-DOS version needs at least a 256K system. Extra memory for a RAM-disk is convenient but not necessary. _5._2. _P_r_e_r_e_q_u_i_s_i_t_e _S_o_f_t_w_a_r_e There are three programs you will need: the IFP interpreter (IFP.EXE), a text editor, and a directory lister. You must sup- ply the text editor and directory lister. (The ``PC-Write'' edi- tor works with IFP under DOS 2.0 and 3.0; ``edlin'' only works under DOS 3.0; I haven't tried any others). All three of these programs must reside on a different disk drive than your IFP functions. If you have enough memory, it is advantageous to put these on a RAM-disk. The IFP function files should be kept on a floppy or hard disk, just in case your machine crashes. December 5, 1985 IFP Reference 13 _5._3. _R_u_n_n_i_n_g _I_F_P Before invoking IFP, two environment variables should be set. The ``EDITOR'' variable should be set to the name of your favorite editor. The default editor is ``c:ed.exe''. The ``FPDIR'' variable should be set to the name of your favorite directory listing program. Normally these variables should be set by the autoexec.bat file. Below is an example autoexec.bat file: set EDITOR = A:edlin.com set IFPDIR = A:sd2.com _5._4. _S_t_a_r_t_i_n_g _I_F_P To start an IFP session, change your current working direc- tory to a directory on the IFP functions disk. Then execute the ``ifp.exe'' program. Your current working directory becomes your current working IFP module. (There is no way to change your current working directory from within IFP. To change it, leave the interpreter and change it within DOS.) When IFP is ready, it will respond with the prompt ``ifp> ''. To end the IFP session, enter the command ``exit''. All function definitions are kept in disk files, so you can't lose anything when you exit or the com- puter crashes. To edit an IFP definition file, type the command: ed name where _n_a_m_e is the name of the function to be edited. (Since all IFP reserved words are upper case, it is a good practice to use lower or mixed case for function names.) The function may be one local to the current working module, or one that is imported into the current working module. If the function name is neither December 5, 1985 IFP Reference 14 defined locally nor imported, then it is assumed to be a new local function. The function definition file must be of the form: DEF name AS f; Definitions are in free format, line breaks are treated as spaces. Matching pairs of ``(*'' and ``*)'' delimit comments as in Pascal. Note: Do not switch to another file from within the editor. Always exit the editor to return to the IFP command interpreter first and then edit the next file. Otherwise inter- preter won't know that its internal copy of a function is invalid. To apply an IFP function, type the command: show object : function; The interpreter evaluates the result of applying the function to the object. The result is then pretty-printed at the terminal. Listing 1 shows a sample session. To list your functions, type the command: dir The directory listing program specified by IFPDIR will be invoked. _N_o_t_e: my directory lister won't work unless I type a trailing slash, i.e. ``dir/". I have not tried any other direc- tory listing programs. To delete a function, type the command: del f The function definition file (along with the memory copy) will be deleted. Wildcards are not permitted in the function name. December 5, 1985 IFP Reference 15 _W_a_r_n_i_n_g: do not try to delete files with extensions (e.g. ``.bak'') from within IFP, since file names are truncated to 8 characters, IFP may delete the wrong file. _5._5. _T_r_a_c_i_n_g _F_u_n_c_t_i_o_n_s Currently, IFP has simple program trace mechanism. To trace a function, respond to the IFP prompt with: trace on f ,f ,...f ; 1 2 n where the f's are functions to be traced. Whenever a traced function is invoked, its argument and result are shown. Also, the argument and result of all called functions are shown. To stop tracing functions, respond to the IFP prompt with: trace off f ,f ,...f ; 1 2 n When tracing, the interpreter ellipses are used to abbrevi- ate functions. You can set the depth at which ellipses occur with the _d_e_p_t_h command: depth n where n is a non-negative integer. The default depth is two. There is also a functional form for creating trace func- tions. Its form is @_s_t_r_i_n_g The function formed always returns its argument unchanged, and it prints ``string: '' followed by its argument. For example, <1 3 5> : EACH @banana END will print the messages: December 5, 1985 IFP Reference 16 banana: 1 banana: 2 banana: 3 This tracing functional form is for debugging only, since it creates a side effect (the message!), it is not truly functional. Program execution can be aborted at any time by pressing control-C. A trace of where the function was will be shown. Pressing control-C again will abort the trace. December 5, 1985