doc/guide/src/ReturnStatement.adoc

   1 ReturnStatement
   2 ===============
   3
   4 Programmers coming from languages that have a `return` statement, such
   5 as C, Java, and Python, often ask how one can translate functions that
   6 return early into SML.  This page briefly describes a number of ways
   7 to translate uses of `return` to SML.
   8
   9 == Conditional iterator function ==
  10
  11 A conditional iterator function, such as
  12 http://www.standardml.org/Basis/list.html#SIG:LIST.find:VAL[`List.find`],
  13 http://www.standardml.org/Basis/list.html#SIG:LIST.exists:VAL[`List.exists`],
  14 or
  15 http://www.standardml.org/Basis/list.html#SIG:LIST.all:VAL[`List.all`]
  16 is probably what you want in most cases.  Unfortunately, it might be
  17 the case that the particular conditional iteration pattern that you
  18 want isn't provided for your data structure.  Usually the best
  19 alternative in such a case is to implement the desired iteration
  20 pattern as a higher-order function.  For example, to implement a
  21 `find` function for arrays (which already exists as
  22 http://www.standardml.org/Basis/array.html#SIG:ARRAY.findi:VAL[`Array.find`])
  23 one could write
  24
  25 [source,sml]
  26 ----
  27 fun find predicate array = let
  28    fun loop i =
  29        if i = Array.length array then
  30           NONE
  31        else if predicate (Array.sub (array, i)) then
  32           SOME (Array.sub (array, i))
  33        else
  34           loop (i+1)
  35 in
  36    loop 0
  37 end
  38 ----
  39
  40 Of course, this technique, while probably the most common case in
  41 practice, applies only if you are essentially iterating over some data
  42 structure.
  43
  44 == Escape handler ==
  45
  46 Probably the most direct way to translate code using `return`
  47 statements is to basically implement `return` using exception
  48 handling.  The mechanism can be packaged into a reusable module with
  49 the signature
  50 (<!ViewGitFile(mltonlib,master,com/ssh/extended-basis/unstable/public/control/exit.sig)>):
  51 [source,sml]
  52 ----
  53 sys::[./bin/InclGitFile.py mltonlib master com/ssh/extended-basis/unstable/public/control/exit.sig 6:]
  54 ----
  55
  56 (<!Cite(HarperEtAl93, Typing First-Class Continuations in ML)>
  57 discusses the typing of a related construct.)  The implementation
  58 (<!ViewGitFile(mltonlib,master,com/ssh/extended-basis/unstable/detail/control/exit.sml)>)
  59 is straightforward:
  60 [source,sml]
  61 ----
  62 sys::[./bin/InclGitFile.py mltonlib master com/ssh/extended-basis/unstable/detail/control/exit.sml 6:]
  63 ----
  64
  65 Here is an example of how one could implement a `find` function given
  66 an `app` function:
  67 [source,sml]
  68 ----
  69 fun appToFind (app : ('a -> unit) -> 'b -> unit)
  70               (predicate : 'a -> bool)
  71               (data : 'b) =
  72     Exit.call
  73        (fn return =>
  74            (app (fn x =>
  75                     if predicate x then
  76                        return (SOME x)
  77                     else
  78                        ())
  79                 data
  80           ; NONE))
  81 ----
  82
  83 In the above, as soon as the expression `predicate x` evaluates to
  84 `true` the `app` invocation is terminated.
  85
  86
  87 == Continuation-passing Style (CPS) ==
  88
  89 A general way to implement complex control patterns is to use
  90 http://en.wikipedia.org/wiki/Continuation-passing_style[CPS].  In CPS,
  91 instead of returning normally, functions invoke a function passed as
  92 an argument.  In general, multiple continuation functions may be
  93 passed as arguments and the ordinary return continuation may also be
  94 used.  As an example, here is a function that finds the leftmost
  95 element of a binary tree satisfying a given predicate:
  96 [source,sml]
  97 ----
  98 datatype 'a tree = LEAF | BRANCH of 'a tree * 'a * 'a tree
  99
 100 fun find predicate = let
 101    fun recurse continue =
 102        fn LEAF =>
 103           continue ()
 104         | BRANCH (lhs, elem, rhs) =>
 105           recurse
 106              (fn () =>
 107                  if predicate elem then
 108                     SOME elem
 109                  else
 110                     recurse continue rhs)
 111              lhs
 112 in
 113    recurse (fn () => NONE)
 114 end
 115 ----
 116
 117 Note that the above function returns as soon as the leftmost element
 118 satisfying the predicate is found.