Return to manCh1.rno CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp

Annotation of 43BSDReno/share/doc/ps2/07.fp/manCh1.rno, revision 1.1

1.1     ! root        1: .\" Copyright (c) 1980 Regents of the University of California.
        !             2: .\" All rights reserved.  The Berkeley software License Agreement
        !             3: .\" specifies the terms and conditions for redistribution.
        !             4: .\"
        !             5: .\"    @(#)manCh1.rno  6.1 (Berkeley) 4/29/86
        !             6: .\"
        !             7: .sp
        !             8: .NS 1 "Background"
        !             9: .sp
        !            10: .pp
        !            11: \fBFP\fP stands for a \fIFunctional Programming\fP language.
        !            12: Functional programs
        !            13: deal with \fIfunctions\fP instead of \fIvalues\fP.
        !            14: There is  no explicit  representation of state, there are
        !            15: no assignment statments, and hence,
        !            16: no variables.
        !            17: Owing to the lack of state, FP functions are free from
        !            18: side-effects;  so we
        !            19: say the FP is \fIapplicative\fP.
        !            20: .pp
        !            21: All functions take one argument and they are evaluated using
        !            22: the single FP
        !            23: operation, \fIapplication\fP (the colon ':' is the apply operator).
        !            24: For example, we read $~+^:^<3~4>~$ as \*(lqapply
        !            25: the function '+' to its argument <3 4>\*(rq.
        !            26: .pp
        !            27: Functional programs express a functional-level combination of
        !            28: their components
        !            29: instead of describing state changes using value-oriented
        !            30: expressions.
        !            31: For example, we write the function returning the
        !            32: \fIsin\fP of the \fIcos\fP
        !            33: of its input, \*(IE $sin(cos(x))$, as:
        !            34: $sin^@^cos$.  This is a \fIfunctional expression\fP, consisting
        !            35: of the single \fIcombining form\fP called \fIcompose\fP ('@'
        !            36: is the compose operator)
        !            37: and its \fIfunctional arguments\fP \fIsin\fP and \fIcos\fP.
        !            38: .pp
        !            39: All combining forms take functions as arguments and return
        !            40: functions as results; functions may either be applied,
        !            41: \*(EG
        !            42: $sin @ cos^:^3$, or used as a functional argument in another functional
        !            43: expression, \*(EG \fItan @ sin @ cos\fP.
        !            44: .pp
        !            45: As we have seen,
        !            46: FP's combining forms allow us to express
        !            47: control abstractions without the use of variables.
        !            48: The \fIapply to all\fP functional form (&)
        !            49: is another case in point.  The function '& exp'
        !            50: exponentiates all the elements of its argument:
        !            51: .sp 4p
        !            52: .EQ I (1.1)
        !            53: "&exp : <1.0 2.0>" ~==~ "<2.718 7.389>"
        !            54: .EN
        !            55: .sp 4p
        !            56: In (1.1)
        !            57: there are
        !            58: no induction variables, nor a
        !            59: loop bounds specification.
        !            60: Moreover, the code is useful for any size argument,
        !            61: so long as the sub-elements of its argument conform to the domain of the
        !            62: \fIexp\fP function.
        !            63: .pp
        !            64: We must change our view of the programming process
        !            65: to adapt to the functional
        !            66: style.
        !            67: Instead of writing down a set of steps that manipulate and assign values,
        !            68: we compose functional expressions
        !            69: using
        !            70: the higher-level functional forms.
        !            71: For example, the function  that adds a
        !            72: scalar to all elements of a vector will be written in two steps.  First,
        !            73: the function that distributes the scalar amongst each element
        !            74: of the vector:
        !            75: .sp 4p
        !            76: .EQ I (1.2)
        !            77: "distl : <3 <4 6>>" ~==~ "<<3 4> <3 6>>"
        !            78: .EN
        !            79: .sp 4p
        !            80: Next, the function that adds the pairs of elements that
        !            81: make up a sequence:
        !            82: .sp 4p
        !            83: .EQ I (1.3)
        !            84: "&+ : <<3 4> <3 6>>" ~==~ "<7 9>"
        !            85: .EN
        !            86: .sp 4p
        !            87: .pp
        !            88: In a value-oriented programming language the computation
        !            89: would be expressed as:
        !            90: .sp 4p
        !            91: .EQ I (1.4)
        !            92: "&+ : distl : <3 <4 6>>,"
        !            93: .EN
        !            94: .sp 4p
        !            95: which means to apply 'distl' to the input and then to apply '+'
        !            96: to every element of the result.
        !            97: In FP we write (1.4) as:
        !            98: .sp 4p
        !            99: .EQ I (1.5)
        !           100: "&+ @ distl : <3 <4 6>>."
        !           101: .EN
        !           102: .sp 4p
        !           103: The functional expression of (1.5) replaces
        !           104: the two step value expression of (1.4).
        !           105: .pp
        !           106: Often,
        !           107: functional expressions are built from the inside out,
        !           108: as in LISP.
        !           109: In the next example we derive a function that scales then
        !           110: shifts a vector, \*(IE for scalars $a,~b^$ and a vector $v vec$,
        !           111: compute $a~+~b v vec$.  This FP function will have three
        !           112: arguments, namely $a,~b~$ and $~v vec$.  Of course, FP
        !           113: does not use formal parameter names, so
        !           114: they will be designated by the function symbols 1, 2, 3.
        !           115: The first code segment scales $v vec~$ by $b$ (defintions
        !           116: are delimited with curly braces '{}'):
        !           117: .sp 4p
        !           118: .EQ I (1.6)
        !           119: "{scaleVec &\(** @ distl @ [2,3]}"
        !           120: .EN
        !           121: .sp 4p
        !           122: The code segment in (1.5)
        !           123: shifts the vector.
        !           124: The completed function is:
        !           125: .sp 4p
        !           126: .EQ I (1.7)
        !           127: "{changeVec &+ @ distl @ [1 , scaleVec]}"
        !           128: .EN
        !           129: .pp
        !           130: In the derivation of the program we wrote from right to left,
        !           131: first doing the \fIdistl\fP's and then composing with the
        !           132: \fIapply-to-all\fP functional form.
        !           133: Using an imperative language, such as Pascal,
        !           134: we  would write the program from
        !           135: the outside in, writing the loop
        !           136: before inserting the arithmetic operators.
        !           137: .pp
        !           138: Although
        !           139: FP encourages a recursive programming style,
        !           140: it provides combining forms to avoid explicit recursion.
        !           141: For example, the
        !           142: right insert  combining form (!)
        !           143: can be used to write a function
        !           144: that adds up a list of numbers:
        !           145: .sp 4p
        !           146: .EQ I (1.8)
        !           147: "!+ : <1 2 3>" ~==~ 6
        !           148: .EN
        !           149: .pp
        !           150: The equivalent, recursive function is much longer:
        !           151: .sp 4p
        !           152: .EQ I (1.9)
        !           153: "{addNumbers (null -> %0 ; + @ [1, addNumbers @ tl])}"
        !           154: .EN
        !           155: .pp
        !           156: The generality of the combining forms encourages hierarchical
        !           157: program development.  Unlike APL,
        !           158: which restricts
        !           159: the use of combining forms to certain builtin functions,
        !           160: FP allows combining forms to take any functional expression as
        !           161: an argument.
        !           162: .bp

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.