6 ms·

> It has built-in maps now! Prolog has always had that. You declare facts like parent(patricia, shelly), and you cant make this at run-time too with assert and

by zvrba 13y ago

> It has built-in maps now! Prolog has always had that. You declare facts like parent(patricia, shelly), and you cant make this at run-time too with assert and retract. Unification & resolution makes this work like a 2-way map. What's the big deal now?

mjn 13y ago
The motivation and comparison to existing alternatives is discussed a bit in these sections: http://www.swi-prolog.org/pldoc/man?section=ext-maps-usage http://www.swi-prolog.org/pldoc/man?section=ext-maps-usage http://www.swi-prolog.org/pldoc/man?section=ext-maps-motivation http://www.swi-prolog.org/pldoc/man?section=ext-maps-motivat...
rdtsc 13y ago
> 5.4.3 When to use maps? > Maps are a new type in the Prolog world Sorry, I'll take SWI-Prolog developers' word over yours in this case. Your argument is a bit like the "Well this old existing language is Turing complete, so why bother with anything".
- danieldk 13y ago
  Your argument is a bit like the "Well this old existing language is Turing complete, so why bother with anything". Except that he is right that Prolog facts (and other clauses) can be used as a mapping. At the very least, modern Prolog implementations index on the first argument (compute the hash code and look that up). So, you get similar properties to a hashmap: you can look up in O(n) time and get an associated atom/term/... However, multiple clauses can match a query. For instance, given foo(bar(x),1). foo(bar(y),2). the query foo(bar(_),X) creates a backtracking point (both facts unify, so X will be bound to x and y subsequently). SWI-Prolog's new maps behave more like normal maps in that there cannot be duplicate keys. However, you could enforce that with Prolog facts as well: assert_unique(parent(X,Y)) :- retractall(parent(X,_), assert(parent(X,Y)). assert_unique(parent(jack,john)) will ensure that any parent(jack,_) facts are removed before asserting the new fact.
  - rdtsc 13y ago
    A prop list can be used as a mapping too. What about integers being keys. Or say de-serializing a nested JSON document to clauses. How does a 3 level deep map work with clauses? > assert_unique(parent(X,Y)) :- retractall(parent(X,_), assert(parent(X,Y)). Maybe to you that looks like an example why maps are _not_ needed as they just reinvent the wheel or something. To me it looks like an example why maps _are_ needed.
    - danieldk 13y ago
      What about integers being keys. That works fine. How does a 3 level deep map work with clauses The most straightforward manner is like you would do this in a relational database (if the goal is to keep O(1) times). E.g. two-level: foo(a,x). foo(b,y). bar(x,a-x-one). bar(x,a-x-two). bar(y,b-y-one). Again, you can add predicates to make this less unwieldy. If the JSON conforms to a schema, there is also the possibility of mapping particular keys to arguments. Since you know the set of possible keys in such a case, you could map keys to fixed term arguments. E.g. a structure such as: { "foo": "apple", "bar": "pear" } Could be mapped to: json(apple,pear) You would have the same You could do this for deeper maps as well. It gives you the same benefits as hash maps, O(1) indexing. In fact, the Hdrug[1] system uses such a representation for partially typed feature structures, which can have an arbitrary depth. It provides a DSL for easily specifying types (the 'schema') and unifying structures and substructures. There is also a short description in the introductory chapters of my thesis, though it is definitely not my work ;). Note: I am not for or against adding maps to the language. There are probably applications where they are very handy in Prolog. For the things I worked on in Prolog I never really needed first-class maps. [1] http://www.let.rug.nl/~vannoord/Hdrug/ http://www.let.rug.nl/~vannoord/Hdrug/ [2] http://danieldk.eu/Research/Publications/phd-thesis.pdf http://danieldk.eu/Research/Publications/phd-thesis.pdf (starting at the end of page 19)
      - hnriot 13y ago
        syringes???
danieldk 13y ago
Unification & resolution makes this work like a 2-way map. In portable Prolog code, you can only really make the assumption that the first argument is indexed, if it is an atom or a term (in the latter case the functor and arity is used). In other words, if you have many parent/2 facts parent(patricia,X). will be a constant-time lookup, while parent(X,shelly). will not be. Another thing to keep in mind is that there can be multiple clauses that unify with a goal. Real-world story: in the natural language generator that I co-developed, we rewrote every grammar rule with term expansion, such that the attribute-value structure for the syntactic head was the first argument. In this manner, lookups of grammar rules are much faster, since you only have to try to unify with the rules with the corresponding syntactic category. tl;dr Prolog facts can be used to create mappings. Don't use them as a two-way map without extra precaution if you have a large number of facts.

by zvrba 13y ago

mjn 13y ago

The motivation and comparison to existing alternatives is discussed a bit in these sections: http://www.swi-prolog.org/pldoc/man?section=ext-maps-usage http://www.swi-prolog.org/pldoc/man?section=ext-maps-usage http://www.swi-prolog.org/pldoc/man?section=ext-maps-motivation http://www.swi-prolog.org/pldoc/man?section=ext-maps-motivat...

rdtsc 13y ago

> 5.4.3 When to use maps? > Maps are a new type in the Prolog world Sorry, I'll take SWI-Prolog developers' word over yours in this case. Your argument is a bit like the "Well this old existing language is Turing complete, so why bother with anything".

danieldk 13y ago
Your argument is a bit like the "Well this old existing language is Turing complete, so why bother with anything". Except that he is right that Prolog facts (and other clauses) can be used as a mapping. At the very least, modern Prolog implementations index on the first argument (compute the hash code and look that up). So, you get similar properties to a hashmap: you can look up in O(n) time and get an associated atom/term/... However, multiple clauses can match a query. For instance, given foo(bar(x),1). foo(bar(y),2). the query foo(bar(_),X) creates a backtracking point (both facts unify, so X will be bound to x and y subsequently). SWI-Prolog's new maps behave more like normal maps in that there cannot be duplicate keys. However, you could enforce that with Prolog facts as well: assert_unique(parent(X,Y)) :- retractall(parent(X,_), assert(parent(X,Y)). assert_unique(parent(jack,john)) will ensure that any parent(jack,_) facts are removed before asserting the new fact.
- rdtsc 13y ago
  A prop list can be used as a mapping too. What about integers being keys. Or say de-serializing a nested JSON document to clauses. How does a 3 level deep map work with clauses? > assert_unique(parent(X,Y)) :- retractall(parent(X,_), assert(parent(X,Y)). Maybe to you that looks like an example why maps are _not_ needed as they just reinvent the wheel or something. To me it looks like an example why maps _are_ needed.
  - danieldk 13y ago
    What about integers being keys. That works fine. How does a 3 level deep map work with clauses The most straightforward manner is like you would do this in a relational database (if the goal is to keep O(1) times). E.g. two-level: foo(a,x). foo(b,y). bar(x,a-x-one). bar(x,a-x-two). bar(y,b-y-one). Again, you can add predicates to make this less unwieldy. If the JSON conforms to a schema, there is also the possibility of mapping particular keys to arguments. Since you know the set of possible keys in such a case, you could map keys to fixed term arguments. E.g. a structure such as: { "foo": "apple", "bar": "pear" } Could be mapped to: json(apple,pear) You would have the same You could do this for deeper maps as well. It gives you the same benefits as hash maps, O(1) indexing. In fact, the Hdrug[1] system uses such a representation for partially typed feature structures, which can have an arbitrary depth. It provides a DSL for easily specifying types (the 'schema') and unifying structures and substructures. There is also a short description in the introductory chapters of my thesis, though it is definitely not my work ;). Note: I am not for or against adding maps to the language. There are probably applications where they are very handy in Prolog. For the things I worked on in Prolog I never really needed first-class maps. [1] http://www.let.rug.nl/~vannoord/Hdrug/ http://www.let.rug.nl/~vannoord/Hdrug/ [2] http://danieldk.eu/Research/Publications/phd-thesis.pdf http://danieldk.eu/Research/Publications/phd-thesis.pdf (starting at the end of page 19)
    - hnriot 13y ago
      syringes???

danieldk 13y ago

Unification & resolution makes this work like a 2-way map. In portable Prolog code, you can only really make the assumption that the first argument is indexed, if it is an atom or a term (in the latter case the functor and arity is used). In other words, if you have many parent/2 facts parent(patricia,X). will be a constant-time lookup, while parent(X,shelly). will not be. Another thing to keep in mind is that there can be multiple clauses that unify with a goal. Real-world story: in the natural language generator that I co-developed, we rewrote every grammar rule with term expansion, such that the attribute-value structure for the syntactic head was the first argument. In this manner, lookups of grammar rules are much faster, since you only have to try to unify with the rules with the corresponding syntactic category. tl;dr Prolog facts can be used to create mappings. Don't use them as a two-way map without extra precaution if you have a large number of facts.