Re: CC Machine in OCaml

Small improvements:

>    Released under the terms of the GNU Lesser General Public License.

Licensed under the Academic Free License version 2.0

> (*
>    span : ('a -> bool) -> 'a list -> 'a list * 'a list
>    An old scheme friend
> 
>    Span splits the list into the longest initial prefix whose elements all
>    satisfy the predicate f, and the remaining tail. Cf. Olin Shivers's SRFI-1.
> *)
> let span f ls =
>   let rec recur = function
>     | [] -> [], []
>     | x::rest ->
> 	if f x then let (prefix, suffix) = recur rest in
> 	x::prefix, suffix
> 	else [], x::rest
>   in
>   recur ls
> ;;

let span f ls =
  let rec recur = function
    | [] -> [], []
    | x::rest as l ->
      if f x then let (prefix, suffix) = recur rest in
      x::prefix, suffix
      else [], l
  in
  recur ls
;;

> (*
>    substitute : term -> var -> value -> term
> 
>    Substitutes v for x in m.
> *)
> let rec substitute m x v =
>   match m with
>   | Value(Base b) -> Value(Base b)
>   | Value(Var y) ->
>       if x=y then Value v
>       else Value(Var y)
>   | Value(Lambda(y,n)) ->
>       if x=y then Value(Lambda(y,n))
>       else let z = gen_var () in
>       Value(Lambda(z, (substitute (substitute n y (Var z)) x v)))
>   | App(n,p) ->
>       App(substitute n x v, substitute p x v)
>   | AppPrim(o, tlist) ->
>       AppPrim(o, (map (fun t -> substitute t x v) tlist))
> ;;

let rec substitute m x v =
  match m with
  | Value(Base b) -> m
  | Value(Var y) ->
      if x=y then Value v
      else m
  | Value(Lambda(y,n)) ->
      if x=y then m
      else let z = gen_var () in
      Value(Lambda(z, (substitute (substitute n y (Var z)) x v)))
  | App(n,p) ->
      App(substitute n x v, substitute p x v)
  | AppPrim(o, tlist) ->
      AppPrim(o, (map (fun t -> substitute t x v) tlist))
;;

-d