4 ms·

ADT -> Abstract Data Type for those who wonder. It means no need to explicitly define the type of a variable, the compiler infer it based on context.

by gbersac 11y ago

evanpw 11y ago
In this context, ADT probably means algebraic data type: https://en.wikipedia.org/wiki/Algebraic_data_type https://en.wikipedia.org/wiki/Algebraic_data_type. And I don't think your definition for abstract data type is right either: usually the language feature that automatically determines types from context is called type inference.
Robin_Message 11y ago
In this case, I think they meant algebraic data type, since they mention it next to "pattern matching". An algebraic data type is generally made up of two things: 1) structs or tuples, which are useful but in most (but not all languages); C/C++ has them for example; and 2) tagged or disjoint unions, which are different from C unions in that you can tell which one of the union choices is being used (A variant is a particular tagged union). Tagged unions are super-useful for pattern matching, so you get code like: match rv { Ok(_) => { None } Err(CacheError::KeyNotFound) => { Some(Resp::NotFound) } Err(ref err) => Some(from_cache_err(err)) } which has a nice syntax, is type-safe and can be compiled reasonably efficiently. The algebraic part means that these two features can be used in any combination with each other, and also refers to the link that, roughly 0 is the empty type, 1 is the unit type, structs correspond to multiplies (and gets called the product type), and unions to plus (so is called a sum type). Why? Because if I have a tuple of a union of A or B or C, and another union of X or Y, I have 6 possible values in total, and (1+1+1) x (1+1) = 6.
- tel 11y ago
  You probably also want to complete your toolkit with functions which are then exponentiation. Also, in any ADT system 0 should be exactly the empty sum and 1 exactly the empty product. This is what makes things hang together properly.
  - _asummers 11y ago
    0 and 1 are just idiomatic though, correct? The important part, from my knowledge of abstract algebra, is that there exist an identity for any operation function () such that for all x in your domain, x () identity = x.
    - tel 11y ago
      Oh sure, you can call them whatever you like. But if you have an ADT system which has a unit type that isn't quite the empty product then you'll be in for an interesting time at least. E.g., this is true in Haskell and it causes there to be some "extra structure" which often has to be smoothed over. Lots of library functions exist just to do this smoothing.
  - fanf2 11y ago
    And differentiation, which is useful for functional update of persistent data structures. https://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ https://chris-taylor.github.io/blog/2013/02/13/the-algebra-o...
    - tel 11y ago
      That's nice, but I wouldn't call it particularly core to ADT systems. It also requires quite a bit more machinery to embed directly since you need to be able to talk about functors/containers.
pjmlp 11y ago
Besides what evanpw already answered. Abstract Data Type were introduced by languages like CLU, Mesa and Modula-2 among others. It means having modules that only export the type names, but not their definition, while exposing functions/procedures to operate in such types. It is not the same as the ADTs in functional languages, although they are quite similar.
- catnaroek 11y ago
  They're not similar at all. Algebraic data types are finite sums and (tensor) products. Abstract data types are existential types, which are infinite sums indexed by a kind.
  - tel 11y ago
    What makes them weak?
    - catnaroek 11y ago
      When you unpack a weak existential type repeatedly, every time you get a fresh new type. When you unpack a strong existential repeatedly, you always get the same type. Anyway, my original comment was wrong: in ML, every time you project a type component from a module, you always get the same type. So it's more like a strong existential. My bad.
      - tel 11y ago
        Ah, gotcha. Thanks!
  - pjmlp 11y ago
    The purpose of my remark is how they look like in terms of usage for the humble programmer. They being similar how having a limited data structure (non extensible) with a set of functions that operate on it. Depending on the FP language ADTs can also partially hide their implementation like the Abstract Data Types in modular languages. But I can also happily discuss the math theory and the denotational semantics about them across languages, but I don't think it will help for many readers.
catnaroek 11y ago
There are two conceptual errors here: (0) Rust doesn't really have much support for abstract data types. What Rust has is something not too unlike Haskell: you can hide `struct` fields [though not `enum` constructors], but the `struct` remains concrete. With a bona fide abstract data type mechanism, as in ML, you can give a module a signature that reveals the existence, but not the representation, of its type components. I'm guessing this much representation hiding isn't fully compatible with Rust's goals, which require knowing the sizes of types statically, unless they're behind a layer of indirection. (1) Abstract data types have no relation whatsoever to type inference. [Nor do algebraic data types for that matter.] An abstract data type is an existential type: a dependent pair consisting of a type `T`, and a value whose type is `F T`, for some type function `F`. The closest thing Rust has to existentials is trait objects, but these can't do everything that existentials can do.
- gpderetta 11y ago
  I'm neither an ML nor Rust expert, but wouldn't Rust trait objects (which are basically type erasure wrappers over traits) approximate abstract data types?
  - catnaroek 11y ago
    With the caveat that there can only be one instance of it.

ADT -> Abstract Data Type for those who wonder. It means no need to explicitly define the type of a variable, the compiler infer it based on context.

by gbersac 11y ago

ADT -> Abstract Data Type for those who wonder. It means no need to explicitly define the type of a variable, the compiler infer it based on context.

evanpw 11y ago

In this context, ADT probably means algebraic data type: https://en.wikipedia.org/wiki/Algebraic_data_type https://en.wikipedia.org/wiki/Algebraic_data_type. And I don't think your definition for abstract data type is right either: usually the language feature that automatically determines types from context is called type inference.

Robin_Message 11y ago

In this case, I think they meant algebraic data type, since they mention it next to "pattern matching". An algebraic data type is generally made up of two things: 1) structs or tuples, which are useful but in most (but not all languages); C/C++ has them for example; and 2) tagged or disjoint unions, which are different from C unions in that you can tell which one of the union choices is being used (A variant is a particular tagged union). Tagged unions are super-useful for pattern matching, so you get code like: match rv { Ok(_) => { None } Err(CacheError::KeyNotFound) => { Some(Resp::NotFound) } Err(ref err) => Some(from_cache_err(err)) } which has a nice syntax, is type-safe and can be compiled reasonably efficiently. The algebraic part means that these two features can be used in any combination with each other, and also refers to the link that, roughly 0 is the empty type, 1 is the unit type, structs correspond to multiplies (and gets called the product type), and unions to plus (so is called a sum type). Why? Because if I have a tuple of a union of A or B or C, and another union of X or Y, I have 6 possible values in total, and (1+1+1) x (1+1) = 6.

tel 11y ago
You probably also want to complete your toolkit with functions which are then exponentiation. Also, in any ADT system 0 should be exactly the empty sum and 1 exactly the empty product. This is what makes things hang together properly.
- _asummers 11y ago
  0 and 1 are just idiomatic though, correct? The important part, from my knowledge of abstract algebra, is that there exist an identity for any operation function () such that for all x in your domain, x () identity = x.
  - tel 11y ago
    Oh sure, you can call them whatever you like. But if you have an ADT system which has a unit type that isn't quite the empty product then you'll be in for an interesting time at least. E.g., this is true in Haskell and it causes there to be some "extra structure" which often has to be smoothed over. Lots of library functions exist just to do this smoothing.
- fanf2 11y ago
  And differentiation, which is useful for functional update of persistent data structures. https://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ https://chris-taylor.github.io/blog/2013/02/13/the-algebra-o...
  - tel 11y ago
    That's nice, but I wouldn't call it particularly core to ADT systems. It also requires quite a bit more machinery to embed directly since you need to be able to talk about functors/containers.

pjmlp 11y ago

Besides what evanpw already answered. Abstract Data Type were introduced by languages like CLU, Mesa and Modula-2 among others. It means having modules that only export the type names, but not their definition, while exposing functions/procedures to operate in such types. It is not the same as the ADTs in functional languages, although they are quite similar.

catnaroek 11y ago
They're not similar at all. Algebraic data types are finite sums and (tensor) products. Abstract data types are existential types, which are infinite sums indexed by a kind.
- tel 11y ago
  What makes them weak?
  - catnaroek 11y ago
    When you unpack a weak existential type repeatedly, every time you get a fresh new type. When you unpack a strong existential repeatedly, you always get the same type. Anyway, my original comment was wrong: in ML, every time you project a type component from a module, you always get the same type. So it's more like a strong existential. My bad.
    - tel 11y ago
      Ah, gotcha. Thanks!
- pjmlp 11y ago
  The purpose of my remark is how they look like in terms of usage for the humble programmer. They being similar how having a limited data structure (non extensible) with a set of functions that operate on it. Depending on the FP language ADTs can also partially hide their implementation like the Abstract Data Types in modular languages. But I can also happily discuss the math theory and the denotational semantics about them across languages, but I don't think it will help for many readers.

catnaroek 11y ago

There are two conceptual errors here: (0) Rust doesn't really have much support for abstract data types. What Rust has is something not too unlike Haskell: you can hide `struct` fields [though not `enum` constructors], but the `struct` remains concrete. With a bona fide abstract data type mechanism, as in ML, you can give a module a signature that reveals the existence, but not the representation, of its type components. I'm guessing this much representation hiding isn't fully compatible with Rust's goals, which require knowing the sizes of types statically, unless they're behind a layer of indirection. (1) Abstract data types have no relation whatsoever to type inference. [Nor do algebraic data types for that matter.] An abstract data type is an existential type: a dependent pair consisting of a type `T`, and a value whose type is `F T`, for some type function `F`. The closest thing Rust has to existentials is trait objects, but these can't do everything that existentials can do.

gpderetta 11y ago
I'm neither an ML nor Rust expert, but wouldn't Rust trait objects (which are basically type erasure wrappers over traits) approximate abstract data types?
- catnaroek 11y ago
  With the caveat that there can only be one instance of it.