Source

ocaml-lib / lambda-noobj.ml

(* objectives: same as lambda.ml but without objects *)
(* not as modular and requires more identifiers *)

type ('a,'b) expr = Expr of 'a

let abs =
  let cpt = ref 0 in
  fun f ->
    let x = incr cpt; !cpt in
    `Abs (x, f (`Var x))
let app u v = `App (u,v)

let eabs (f : ('a,'b) expr -> ('a,'c) expr) : ('a,'b -> 'c) expr =
  Expr (abs (fun x -> let Expr y = f (Expr x) in y))
let eapp (Expr u : ('a,'b -> 'c) expr) (Expr v : ('a,'b) expr) : ('a,'c) expr =
  Expr (app u v)

let subst subst_rec env t =
  match t with
  | `Var x ->
      (try List.assoc x env
      with Not_found -> t)
  | `Abs (x,v) ->
      `Abs (x, subst_rec env v)
  | `App (u,v) ->
      `App (subst_rec env u, subst_rec env v)

let reduce reduce_rec subst_rec t =
  match t with
  | `Var _ -> t
  | `Abs (x,v) -> `Abs (x, reduce_rec v)
  | `App (u,v) ->
      match reduce_rec u with
      | `Abs (x,w) -> reduce_rec (subst_rec [(x,v)] w)
      | u' -> `App (u', reduce_rec v)

let to_string to_string_rec t =
  match t with
  | `Var x -> "x" ^ string_of_int x
  | `Abs (x,v) -> "x" ^ string_of_int x ^ "\\" ^ to_string_rec v
  | `App (u,v) -> "(" ^ to_string_rec u ^ " " ^ to_string_rec v ^ ")"


type 'a case1 = [ `Var of int | `Abs of int * 'a | `App of 'a * 'a ]
type term1 = 'a case1 as 'a
type 'b eterm1 = (term1 case1, 'b) expr

let rec subst1 env t = subst subst1 env t
let rec reduce1 t = reduce reduce1 subst1 t
let rec to_string1 t = to_string to_string1 t

let test () =
  let t : term1 = abs (fun p2 -> abs (fun np -> abs (fun x -> app np (abs (fun y -> app (app p2 x) y))))) in
  let t1 = reduce1 t in
  to_string1 t1

let etest () =
  let Expr t =
    eabs (fun (p2 : ('a,'e -> 'e -> 's) expr) ->
      eabs (fun (np : ('a,('e -> 's) -> 's) expr) ->
	eabs (fun x ->
	  eapp np
	    (eabs (fun y ->
	      eapp (eapp p2 x) y))))) in
  let t1 = reduce1 t in
  to_string1 t1
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.