S-expression Tree to Abstract Syntax Tree in OCaml

Question

I'm implementing a symbolic language in OCaml and have been struggling to translate my s-expression tree into an abstract syntax tree.

The s-expression tree is

(* sexpr.mli *)
type atom =
   | Atom_unit
   | Atom_int  of int
   | Atom_sym  of string

type expr =
   | Expr_atom of atom
   | Expr_list of expr list

The abstract syntax tree is

(* ast.ml *)
open Sexpr

type sym = string

(* abstract syntax tree nodes *)
type expr =
   | Expr_unit
   | Expr_int    of int
   | Expr_sym    of sym

(* Sexp.atom -> Ast.expr *)
let ast_of_atom a =
   match a with
      | Atom_unit  -> Expr_unit
      | Atom_int n -> Expr_int n
      | Atom_sym s -> Expr_sym s

(* Sexp.expr -> Ast.expr *)
let rec ast_of_sexpr sx = match sx with
    | Expr_atom a -> ast_of_atom a
    | Expr_list l -> 
    match l with
       | []   -> ast_of_atom Atom_unit
       | [x]  -> ast_of_sexpr x
       | h::t -> ignore ( ast_of_sexpr h ); ast_of_sexpr ( Expr_list t )

The function ast_of_sexpr needs to conform with the type signature

val ast_of_sexpr : Sexpr.expr -> expr.

This is my challenge; I can't figure out a way, that conforms with the type signature, to recurse into the s-expression tree (i.e. nested lists) and translate s-expression tree nodes to abstract syntax tree nodes.

In an ideal world, I could evaluate the list head and recurse over the tail in one expression. I've tried to emulate this ideal using sequencing. But this, of course, ignores the left-side value and will only output the last value when printing a parsed stream of tokens.

Can anyone suggest a method for evaluating the list head, without ignoring the value, and recursing deeper into the s-expression tree? I'm even open to reading better solutions for translating between the two trees.

Answer 1

The Ast.expr type definition looks wrong: it does not represent an abstract syntax tree, but merely the syntax of an atomic expression. This is because the type is not recursive at all, so it can hardly be called a tree. By comparison, Sexp.expr is a recursive type.

My guess is that you forgot a case in the type definition, for instance:

type expr =
   | Expr_unit
   | Expr_int    of int
   | Expr_sym    of sym
   | Expr_call   of expr list

Once this is done, the two types are practically the same, so conversion becomes simple.

Answer 2

Very generally, here's how to calculate some values "without ignoring them":

let v = <calculate> in
let w = <calculate> in
<expression using v and w>

I'm not sure this is what you're asking, but this is a conceptual difficulty for people starting with OCaml (IMHO).