8.1 Recursive definitions of values

(Introduced in Objective Caml 1.00)

As mentioned in section 7.7.2, the letrec bindingconstruct, in addition to the definition of recursive functions,also supports a certain class of recursive definitions ofnon-functional values, such as

letrecname₁=1:: name₂and name₂=2:: name₁in expr

which binds name₁ to the cyclic list 1::2::1::2::…, andname₂ to the cyclic list 2::1::2::1::…Informally, the class of accepted definitions consists of thosedefinitions where the defined names occur only inside functionbodies or as argument to a data constructor.

More precisely, consider the expression:

letrecname₁= expr₁and … and name_n= expr_nin expr

It will be accepted if each one of expr₁ … expr_n isstatically constructive with respect to name₁ … name_n,is not immediately linked to any of name₁ … name_n,and is not an array constructor whose arguments have abstract type.

An expression e is said to be statically constructivewith respect to the variables name₁ … name_n if at leastone of the following conditions is true:

• e has no free occurrence of any of name1 … namen
• e is a variable
• e has the form fun … -> …
• e has the form function … -> …
• e has the form lazy( … )

• e has one of the following forms, where each one ofexpr1 … exprm is statically constructive with respect toname1 … namen, and expr0 is statically constructive withrespect to name1 … namen, xname1 … xnamem:

  • let [rec] xname1= expr1and …and xnamem= exprmin expr0
  • letmodule … inexpr1
  • constr( expr1, … , exprm)
  • `tag-name( expr1, … , exprm)
  • [|expr1; … ; exprm|]
  • {field1= expr1; … ; fieldm = exprm}
  • {expr1with field2= expr2; … ; fieldm = exprm} where expr1 is not immediatelylinked to name1 … namen
  • (expr1, … , exprm)
  • expr1; … ; exprmAn expression e is said to be immediately linked to the variablename in the following cases:

• e is name

• e has the form expr1; … ; exprm where exprmis immediately linked to name
• e has the form let [rec] xname1= expr1and …and xnamem= exprmin expr0 where expr0 is immediatelylinked to name or to one of the xnamei such that expriis immediately linked to name.