> Would you say Traits in rust aren't an OO construct?

I'd say traits in Rust, typeclasses in Haskell and Scala imlicit views are the equivalent to Clojure/Script protocols. And similarly, those constructs by themself aren't OOP. I think a simple proof is that if they were, then all OOP languages would have them. But because there are OOP languages (the most popular ones at that) which don't have them, then it follows this construct is not fundamental to OOP.

> But a record defines implementations of the protocol methods.

It's better to think of it as a protocol is extended to a type. It is not the record which defines the implementation. The methods don't belong to the record, they are independently defined, they can come from a dependency, they can even be shared with other types and other protocols. This is contrary to objects which define their own methods.

> The data and methods are coupled in the record definition.

Functions are associated with a protocol and a type independently of the record or protocol definition. This association is many to many. The same function can be associated over many protocols and many types. There is no coupling. You can even dissociate them. To add new associations or dissociate existing ones, you don't need to touch the record definition at all.

> The methods depend on having the records fields in scope.

They don't. Record fields aren't scoped to their associated methods. They are always public. There is no self or this scope. They are just normal functions like any other. You don't even need a protocol. Just write a function which takes a record and does something with it. Now if you want to make this function type polymorphic, you can use a protocol.

I'm not sure I'm explaining myself very well. Think of an object. The object defines some data fields. And it defines some methods together. You can't use those methods with other objects. The ownership is tied to the object that defined them. The only way to share the methods is through inheritance. Similarly, you can only manipulate the data fields of an object through the object, because the object owns the access to them. Only if it chooses to make them public or expose a getter/setter are other objects allowed access. This is OOP. If you model your programs with objects like that, you are doing object oriented programming. Data is encapsulated behind objects, and can only be manipulated through sending a message (a method call) to the object. The object defines the set of possible methods for that data. You can't do that in Clojure/Script, because no object like construct exists that would allow you to do it.

Now in Clojure/Script, you have datatypes. That is, data with an associated type. You can create custom ones, such as records. A record is a set of key/value pairs with an associated type. A Person record defines a type Person, with keys Age and Weight and their values. That's all a record does. It can't restrict access to its data, it can't expose methods, and it can't receive messages (method calls). You can now write functions that take input of this new type. Those functions can be defined anywhere. They have no special access to the data inside Person, there's no `this` or `self`. The functions don't live inside the datatype. Now, if you want a common set of functions to work over many different types, you can specify a protocol. That's all a protocol does. This is just functional programming.

Sorry for the length. The distinctions are subtle, couldn't find a way to explain them with less words.