(* CMSC 330 Project - Scheme Parser & Interpreter *)
 
(* NAME: *)
 
(* To load this file into the OCaml interpreter, type
 
   #use "scheme.ml"
 
   at the OCaml prompt
*)
 
#load "str.cma"

(* Use this as your abstract syntax tree *)
type ast =
  | Id of string
  | Num of int
  | Bool of bool
  | String of string
  | List of ast list

(* An unparser turns an AST back into a string.  You may find this
   unparser handy in writing this project *)
let rec unparse_list = function
  | [] -> ""
  | (x::[]) -> unparse x
  | (x::xs) -> (unparse x) ^ " " ^ (unparse_list xs)

and unparse = function
  | Id id -> id
  | Num n -> string_of_int n
  | Bool true -> "#t"
  | Bool false -> "#f"
  | String s -> "\"" ^ s ^ "\""
  | List l -> "(" ^ unparse_list l ^ ")"

(************************************************************************)
(* Scanner *)

type token =
 | Tok_Id of string
 | Tok_Num of int
 | Tok_String of string
 | Tok_True
 | Tok_False
 | Tok_LParen
 | Tok_RParen
 | Tok_END
 
(* 1 char tokens *)
let re_lparen = Str.regexp "("
let re_rparen = Str.regexp ")"
 
(* 2 char tokens *)
let re_true = Str.regexp "#t"
let re_false = Str.regexp "#f"
 
(* variable char tokens *)
let re_id = Str.regexp "[a-zA-Z=*+/<>!?-][a-zA-Z0-9=*+/<>!?-]*"
let re_num = Str.regexp "[-]*[0-9]+"
let re_string = Str.regexp "\"[^\"]*\""
let re_whitespace = Str.regexp "[ \t\n]"
 
exception Lex_error of int
 
let tokenize s =
 let rec tokenize' pos s =
   if pos >= String.length s then
     [Tok_END]
   else begin
     if (Str.string_match re_lparen s pos) then
       Tok_LParen::(tokenize' (pos+1) s)
     else if (Str.string_match re_rparen s pos) then
       Tok_RParen::(tokenize' (pos+1) s)
     else if (Str.string_match re_true s pos) then
       Tok_True::(tokenize' (pos+2) s)
     else if (Str.string_match re_false s pos) then
       Tok_False::(tokenize' (pos+2) s)
     else if (Str.string_match re_id s pos) then
       let token = Str.matched_string s in
       let new_pos = Str.match_end () in
       (Tok_Id token)::(tokenize' new_pos s)
     else if (Str.string_match re_string s pos) then
       let token = Str.matched_string s in
       let new_pos = Str.match_end () in
       let tok = Tok_String (String.sub token 1 ((String.length token)-2)) in
       tok::(tokenize' new_pos s)
     else if (Str.string_match re_num s pos) then
       let token = Str.matched_string s in
       let new_pos = Str.match_end () in
       (Tok_Num (int_of_string token))::(tokenize' new_pos s)
     else if (Str.string_match re_whitespace s pos) then
       tokenize' (Str.match_end ()) s
     else
       raise (Lex_error pos)
   end
 in
 tokenize' 0 s


(************************************************************************)
(* Your parser goes here *)

let rec parse_S lst = ((Bool false), lst) (* TO DO *)

and parse_L lst = lst (* TO DO *)
;;

type value =
    Val_Num of int
  | Val_Bool of bool
  | Val_String of string
  | Val_Null
  | Val_Cons of value * value
  | Val_Define of (string * value) list
  | Val_Closure (* of ... *) (* TO DO *)

(* The following function may come in handy *)
let rec string_of_value = function
    Val_Num n -> string_of_int n
  | Val_Bool true -> "#t"
  | Val_Bool false -> "#f"
  | Val_String s -> "\"" ^ s ^ "\""
  | Val_Null -> "null"
  | Val_Cons (v1, v2) -> "(cons " ^ (string_of_value v1) ^ " " ^
      (string_of_value v2) ^ ")"
  | Val_Define v -> "<define>"
  | Val_Closure -> "<closure>"

let parse lst =
  let (ast,lst2) = (parse_S lst) in ast
;;

(************************************************************************)
(* Write your evaluator here *)

let rec eval env ast = Val_Null (* TO DO *)