Procedural parameter

Procedural parameter

In computing, a procedural parameter is a parameter of a procedure that is itself a procedure.

This concept is an extremely powerful and versatile programming tool, because it allows programmers to modify certain steps of a library procedure in arbitrarily complicated ways, without having to understand or modify the code of that procedure.

This tool is particularly effective and convenient in languages that support local function definitions, such as Pascal and the modern GNU dialect of C. It is even more so when function closures are available. The same functionality (and more) is provided by objects in object oriented programming languages, but at a significantly higher cost.

Basic concept

In most languages that provide this feature, a procedural parameter "f" of a subroutine "P" can be called inside the body of "P" as if it were an ordinary procedure:

procedure "P"("f"): return "f"(6,3) * "f"(2,1)

When calling the subroutine "P", one must give it one argument, that must be some previously defined function compatible with the way "P" uses its parameter "f". For example, if we define

procedure "plus"("x", "y"): return "x" + "y"

then we may call "P" ("plus"), and the result will be "plus"(6,3) * "plus"(2,1) = (6 + 3)*(2 + 1) = 27. On the other hand, if we define

procedure "quot"("u", "v"): return "u"/"v"

then the call "P" ("quot") will return "quot"(6,3)*"quot"(2,1) = (6/3)*(2/1) = 4. Finally, if we define

procedure "evil"("z") return z + 100

then the call "P" ("evil") will not make much sense, and may be flagged as an error.

yntactic details

Some programming languages that have this feature may allow or require a complete type declaration for each procedural parameter "f", including the number and type of its arguments, and the type of its result, if any. For example, in the C programming language the example above could be written as

int P ( int f (int a, int b) ) { return f(6,3) * f(2,1); }

In principle, the actual function "actf" that is passed as argument when "P" is called must be type-compatible with the declared type of the procedure parameter "f". This usually means that "actf" and "f" must return the same type of result, must have the same number of arguments, and corresponding arguments must have the same type. The names of the arguments need not be the same, however, as shown by the "plus" and "quot" examples above. However, some programming languages may me more restrictive or more liberal in this regard.

coping

In languages that allow procedural parameters, the scoping rules are usually defined in such a way that procedural parameters are executed in their native scope. More precisely, suppose that the function "actf" is passed as argument to "P", as its procedural parameter "f"; and "f" is then called from inside the body of "P". While "actf" is being executed, it sees the environment of its definition.

The implementation of these scoping rules is not trivial. By the time that "actf" is finally executed, the procedure call frame(s) where its environment variables live may be arbitrarily deep in the stack. This is the so-called downwards funarg problem.

Example: Generic insertion sort

The concept of procedural parameter is best explained by examples. A typical application is the following generic implementation of the insertion sort algorithm, that takes two integer parameters "a","b" and two procedural parameters "prec", "swap":

procedure "isort"("a", "b", "prec", "swap"): integer "i", "j"; "i" gets "a"; while "i" leq "b" do "j" gets "i" while "j" > "a" and "prec"("j", "j"−1) do "swap"("j", "j"−1); "j" gets "j"−1 "i" gets "i"+1

This procedure can be used to sort the elements "x" ["a"] through "x" ["b"] of some array "x", of arbitrary type, in a user-specified order. The parameters "prec" and "swap" should be two functions, defined by the client, both taking two integers "r", "s" between "a" and "b". The "prec" function should return true if and only if the data stored in "x" ["r"] should precede the data stored in "x" ["s"] , in the ordering defined by the client. The "swap" function should exchange the contents of "x" ["r"] and "x" ["s"] , and return no result.

By the proper choice of the functions "prec" and "swap", the same "isort" procedure can be used to reorder arrays of any data type, stored in any medium and organized in any data structure that provides indexed access to individual array elements. (Note however that there are sorting algorithms that are much more efficient than insertion sort for large arrays.)

orting floating-point numbers

For instance, we can sort an array "z" of 20 floating-point numbers, "z" [1] through "z" [20] in increasing order by calling "isort" (1, 20,"zprec","zswap"), where the functions "zprec" and "zswap" are defined as

procedure "zprec"("r","s"): return ("z" ["r"] < "z" ["s"] )

procedure "zswap"("r","s"): float "t"; "t" gets "z" ["r"] ; "z" ["r"] gets "z" ["s"] ; "z" ["s"] gets "t"

orting rows of a matrix

For another example, let "M" be a matrix of integers with 10 rows and 20 columns, with indices starting at 1. The following code will rearrange the elements in each row so that all the even values come before all odd values:

integer i procedure "eoprec"("r", "s"): return ("M" ["i","r"] mod 2) < ("M" ["i","s"] mod 2)

procedure "eoswap"("r", "s"): integer "t"; "t" gets "M" ["i","r"] ; "M" ["i","r"] gets "M" ["i","s"] ; "M" ["i","s"] gets "t"

for "i" from 1 to 10 do "isort"(1, 20, eoprec, eoswap)

Note that the effects of "eoprec" and "eoswap" depend on the row number "i", but the "isort" procedure does not need to know that.

Vector-sorting procedure

The following example uses "isort" to define a procedure "vecsort" that takes an integer "n" and an integer vector "v" with elements "v" [0] through "v" ["n"−1] and sorts them in either increasing or decreasing order, depending on whether a third parameter "incr" is true or false, respectively:

procedure "vecsort"("n", "v", "incr"):

procedure "vprec"("r", "s"): if "incr" then return "v" ["r"] < "v" ["s"] else return "v" ["r"] > "v" ["s"]

procedure "vswap"("r", "s"): integer "t"; "t" gets "v" ["r"] ; "v" ["r"] gets "v" ["s"] ; "v" ["s"] gets "t"

"isort"(0, "n"−1, "vprec", "vswap")

Note the use of nested function definitions to get a function "vprec" whose effect depends on the parameter "incr" passed to "vecsort". In languages that do not allow nested function definitions, like standard C, obtaining this effect would require rather complicated and/or thread-unsafe code.

Example: merging two sequences

The following example illustrates the use of procedural parameters to process abstract data structures independently of their concrete implementation. The problem is to merge two ordered sequences of records into a single sorted sequence, where the nature of the records and the ordering criterion can be chosen by the client. The following implementation assumes only that each record can be referenced by a memory address, and there is a "null address" Λ that is not the address of any valid record. The client must provide the addresses "A", "B" of the first records in each sequence, and functions "prec", "next", and "append", to be described later.

procedure "merge"("A", "B", "prec", "nextA", "appendA", "nextB", "appendB"): address "ini", "fin", "t" "ini" gets Λ; "fin" gets Λ while "A" eq Λ or "B" eq Λ do if "B" = Λ or ("A" eq Λ and "B" eq Λ and "prec"("A","B")) then "t" gets "nextA"("A") "fin" gets appendA("A", "fin"); if "ini" = Λ then "ini" gets "fin" "A" gets "t" else "t" gets "nextB"("B") "fin" gets "appendB"("B", "fin"); if "ini" = Λ then "ini" gets "fin" "B" gets "t" return "ini"

The function "prec" should take the addresses "r", "s" of two records, one from each sequence, and return true if the first record should come before the other in the output sequence. The function "nextA" should take the address of a record from the first sequence, and return the address of the next record in the same sequence, or Λ if there is none. The function "appendA" should append the first record from sequence "A" to the output sequence; its arguments are the address "A" of the record to be appended, and the address "fin" of the last record of the output list (or Λ if that list is still empty). The procedure "appendA" should return the updated address of the final element of the output list. The procedures "nextB" and "appendB" are analogous for the other input sequence.

Merging linked lists

To illustrate the use of the generic merge procedure, here is the code for merging two simple linked lists, starting with nodes at addresses "R", "S". Here we assume that each record "x" contains an integer field "x"."INFO" and an address field "x"."NEXT" that points to the next node; where the "info" fields are in icnreasing order in each list. The input lists are dismantled by the merge, and their nodes are used to build the output list.

procedure "listmerge"("R", "S"):

procedure "prec"("r", "s"): return "r"."INFO" < "s"."INFO"

procedure "next"("x"): return "x"."NEXT"

procedure "append"("x", "fin") if "fin" eq Λ then "fin"."NEXT" gets "x" "x"."NEXT" gets Λ return "x" return "merge"("R", "S", "prec", "next", "append", "next", "append")

Merging vectors

The following code illustrates the independence of the generic "merge" procedure from the actual representation of the sequences. It merges the elements of two ordinary arrays "U" [0] through "U" ["m"−1] and "V" [0] through "V" ["n"−1] of floating-point numbers, in decreasing order. The input arrays are not modified, and the merged sequence of values is stored into a third vector "W" [0] through "W" ["m"+"n"−1] . As in the C programming language, we assume that the expression "&amp;"V" yields the address of variable "V", "*"p" yields the variable whose address is the value of "p", and that "&amp;("X" ["i"] )" is equivalent to "&amp("X" [0] ) + "i" for any array "X" and any integer "i".

procedure "arraymerge"("U", "m", "V", "n", "W"):

procedure "prec"("r", "s"): return (*"r") > (*"s")

procedure "nextU"("x"): if "x" = &amp;("U" ["m"−1] ) then return Λ else return "x" + 1

procedure "nextV"("x"): if "x" = &amp;("V" ["n"−1] ) then return Λ else return "x" + 1

procedure "append"("x", "fin") if "fin" = Λ then "fin" gets &amp;("W" [0] ) (*"fin") gets (*"x") return "fin" + 1 if "m" = 0 then "U" gets Λ if "n" = 0 then "V" gets Λ return "merge"("U", "V", "prec", "nextU", "append", "nextV", "append")

Example: Definite integral

Integrating over an interval

The following procedure computes the approximate integral extstyleint_a^b "f" ("x") d"x" of a given real-valued function "f" over a given interval ["a","b"] of the real line. The numerical method used is the trapezium rule with a given number "n" of steps; the real numbers are approximated by floating-point numbers.

procedure "Intg"("f", "a", "b", "n"): float "t", "x", "s"; integer "i" if "b" = "a" then return 0 "x" gets "a"; "s" gets "f"("a")/2; for i from 1 to "n"−1 do "t" gets "i"/("n"+1); "x" gets (1−"t")*"a" + "t"*"b"; "s" gets "s" + "f"("x") "s" gets "f"("b")/2 return ("b"−"a")*"s"/"n"

Integrating over a disk

Consider now the problem of integrating a given function "g", with two arguments, over a disk "D" with given center ("xc","yc") and given radius "R". This problem can be reduced to two nested single-variable integrals by the change of variables

int!int_D g(x,y), mathrm{d}x, mathrm{d}y = int_0^R z left(int_0^{2pi} g(mathit{xc}+z cos t ,mathit{yc}+z sin t ) ,mathrm{d}t ight),mathrm{d}z

The following code implements the right-hand-side formula:

procedure "DiskIntg"("g", "xc", "yc", "R", "n")

procedure "gring"("z"):

procedure "gpolar"("t"): float "x", "y" "x" gets "xc" + "z"*"cos"("t") "y" gets "yc" + "z"*"sin"("t") return "g"("x", "y")

integer "m" gets "round"("n"*"z"/"R") return "z"*"Intg"("gpolar", 0, 2*π, "m")

return "Intg"("gring", 0, "R", "n")

This code uses the integration procedure "Intg" in two levels. The outer level (last line) uses "Intg" to compute the integral of "gring"("z") for "z" varying from 0 to "R". The inner level (next-to-last line) defines "gring"("z") as being the line integral of "g"("x","y") over the circle with center ("xc","yc") and radius "z".

History

Procedural parameters were invented before the age of electronic computers, by mathematician Alonzo Church, as part of his lambda calculus model of computation.

Procedural parameters as a programming language feature were introduced by ALGOL 60. In fact, ALGOL 60 had a powerful "call by name" parameter-passing mechanism that could simplify some uses of procedural parameters; see Jensen's Device.

Procedural parameters were an essential feature of the LISP programming language, which also introduced the concept of function closure or funarg. They were also introduced into the C programming language , but were little used in that language due to its requirement that all functions be defeined at the outermost (global) scope of the program. They were provided also in Pascal, which allowed nested definitions; however, since standard Pascal did not allow separate compilation, the feature was little used in that language, too.

ee also

*Functional programming
*Funarg problem
*Design patterns (computer science)


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Procedural texture — A procedural texture is a computer generated image created using an algorithm intended to create a realistic representation of natural elements such as wood, marble, granite, metal, stone, and others.Usually, the natural look of the rendered… …   Wikipedia

  • Verilog Procedural Interface — The Verilog Procedural Interface (VPI) is an interface primarily intended for the C programming language. It allows behavioral Verilog code to invoke C functions, and C functions to invoke standard Verilog system tasks. The IEEE 1364 2005… …   Wikipedia

  • процедурный параметр — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN procedural parameter …   Справочник технического переводчика

  • Comparison of programming paradigms — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

  • Null (SQL) — The Greek lowercase omega (ω) character is used to represent Null in database theory. Null is a special marker used in Structured Query Language (SQL) to indicate that a data value does not exist in the database. Introduced by the creator of the… …   Wikipedia

  • Verilog — In the semiconductor and electronic design industry, Verilog is a hardware description language (HDL) used to model electronic systems. Verilog HDL , not to be confused with VHDL, is most commonly used in the design, verification, and… …   Wikipedia

  • List of programming languages by category — Programming language lists Alphabetical Categorical Chronological Generational This is a list of programming languages grouped by category. Some languages are listed in multiple categories. Contents …   Wikipedia

  • Euphoria (programming language) — Euphoria openEuphoria logo Paradigm(s) Imperative, procedural Appeared in 1993 Designed by Jeremy Cowgar, Robert Craig (original), Matt Lewis, Derek Parnell …   Wikipedia

  • Comparison of Java and C++ — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • C (programming language) — C The C Programming Language[1] (aka K R ) is the seminal book on C …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”