(OCaml) Strange syntax used in queue.ml - Operator `<-`

Question

While viewing the Caml Light library for programming examples, I came across the following code taken from the Caml Light queue.ml :

 type 'a queue_cell = Nil | Cons of 'a * 'a queue_cell ref ;; type 'at = { mutable head: 'a queue_cell; mutable tail: 'a queue_cell } ;; let add x = function { head = h; tail = Nil as t } -> (* if tail = Nil then head = Nil *) let c = Cons(x, ref Nil) in h <- c; t <- c | { tail = Cons(_, ref newtail) as oldtail } -> let c = Cons(x, ref Nil) in newtail <- c; oldtail <- c ;; 

This implementation of FIFO data structures puzzles me. I get the general idea to keep a pointer to the last record in the structure, so adding at the end is possible. That makes sense to me. However, this is the syntax of how this is done, which scares me.

Consider the following:

  | { tail = Cons(_, ref newtail) as oldtail } -> let c = Cons(x, ref Nil) in newtail <- c; oldtail <- c 

I have a type problem here. By definition, type newtail should be of type 'a queue cell , since it is extracted using Cons(_, ref newtail) in comparison with the pattern: if I understand correctly, this means that newtail binds the value pointed by the second member of the tail entry field (which is originally a link).

So what does newtail <- c mean? If I try to replace this operator with (fun x -> x <- c) newtail , I get The identifier x is not mutable. , while the code seems to me completely similar to the original version.

Rewriting these few lines to read as follows means the same thing?

  | { tail = Cons(_, newtail) as oldtail } -> let c = Cons(x, ref Nil) in newtail := c; oldtail <- c 

Taking the question one step further, what does the following code actually do?

 type t = Nil | Node of (t ref);; type box = {mutable field: t};; let poke = function | {field = Node(ref n)} -> n <- Nil | {field = Nil} -> () ;; let test = {field = Node(ref (Node(ref Nil)))};; poke test;; test;; 

Write the same way

 {field = Node(n)} -> n := Nil 

and

 {field = Node(ref n)} -> n <- Nil 

?

Even a stranger: the following code returns The value identifier a is unbound.

 let a = Nil;; a <- Nil;; (* The value identifier a is unbound. *) 

Can someone spend time clarifying the use of <- for me? The various examples here are quite perplexing to me ...
Thank you

EDIT: This was originally sent to the Caml mailing list, but I thought the message didn't work out, so I posted it here. It seems that the wiring really worked; sorry for this: link to the mailing list response (which was also published by its author) https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00190.html .

Answer 1

See my answer on the caml list

Why ask the same question twice in different places? This only leads to duplication of efforts when knowledgeable people spend their time to answer you. If you want to do this, please at least send cross-references (from your stackoverflow message to the list archive and vice versa [1]) so that people can verify that it has not yet received a response elsewhere.

[1] yes, you may have circular cross-references since the stackoverflow post has changed!

The semantics of mutable fields and links have changed a lot (forever) between Caml Light and Objective Caml. Remember that this code is Caml Light specific - and if you want to learn Caml, you should rather use Objective Caml, whose implementation is preserved. In Objective Caml, only the record fields are mutable. References are derived from the concept, the type 'ref is defined as:

 type 'a ref = { mutable contents : 'a } 

You change the mutable field with the syntax foo.bar <- baz (where "bar" is the record field, and foo and baz are any expression, foo is the record type)

In Caml Light, record fields are mutable, but sum type fields (options) are mutable; Modified field options, however, are not used here. See http://caml.inria.fr/pub/docs/manual-caml-light/node4.6.html for documentation.

In Caml Light, a record can return a mutable location, an affinity for lvalue in C-like languages. For example, with a mutable option

 type foo = Foo of mutable int 

You can write:

 let set_foo (f : foo) (n : int) = match f with | Foo loc -> loc <- n 

"foo <- bar" is used here to assign the value "bar" lvalue "foo" associated with a mutable pattern. Your example uses two mutable templates:

  | { tail = Cons(_, ref newtail) as oldtail } -> 

• oldtail is a mutable template denoting a mutable "tail" field record

• (ref newtail) is a special syntax, a template for links. It links the modified "newtail" template corresponding to the location of the link. In other words, in Caml Light you can write the operator:: = as such:

  let the prefix: = rv = match r with | ref loc → loc <- v

Hope this helps.

.

Edit:

About a strange error message: I think that inside Caml Light maintains a list of "value identifiers" in the area that come from the template corresponding to the field to be changed (record or option). When they see the expression foo <- bar , they look into this environment to find the appropriate location. Such an environment is local to expression, it never escapes. In particular, when filling is empty, it is empty, and errors indicate that in the region there is no identifier for the value (variable template).

There is one more thing: the namespace of value identifiers and ordinary identifiers is no different. When you match a value identifier, Caml Light adds a value identifier (mutable) to the area, but also the corresponding identifier with the matching rvalue value. This can be quite confusing as you can change the location, but the value will not change:

 #match ref 1 with (ref x) -> (x <- 2; x);; - : int = 1 #match ref 1 with (ref x) as a -> (x <- 2; !a);; - : int = 2 

The identifier (value) will obscure any old identifier (value identifier or not)

 #let x = 1 in let (ref x) = ref 2 in x;; - : int = 2 

(If you did not know, let pattern = e1 in e2 equivalent to match e1 with pattern -> e2 (except for the type system))

Since the syntax classes for identifiers and value identifiers are the same, a non-variable identifier also obscures the value identifier, giving rise to another error:

 #let (ref x) = ref 2 in let x = 1 in x <- 3;; Toplevel input: >let (ref x) = ref 2 in let x = 1 in x <- 3;; > ^^^^^^ The identifier x is not mutable. 

Answer 2

In OCaml, the <- operator mutates mutable fields or instance variables of an object (links are mutated with := ). However, there are other things like ref in your pattern matching that are unfamiliar to me. I think this signals Caml Light to match the cell as a reference (similar to lazy in pattern matches in OCaml), resulting in a variable that is viable as the left side <- for mutation. Passing a variable to a function passes the value of a variable that is not changed, and therefore the function cannot mutate it.

So: it looks like the new tail matches ref newtail sets newtail as a sugared name, so the newtail score newtail converted to !newtail' (where newtail' is some internal name representing the link itself) and newtail <- foo converted to newtail' := foo .

I really don't know Caml Light, and I am not familiar with this saccharification even if it exists in OCaml (the code you provided does not compile in OCaml), but it seems to be happening to me.