dennis@boulder.Colorado.EDU (Dennis Heimbigner) (09/19/90)
I have only recently begun to look at SML and I am curious as to the best method for representing functions that are defined by specifying a set of pairs of values, where the set contents varies over time. This is more-or-less analogous to prolog assert/retract or to functional data base model base functions. For example, I want to associate the set of pairs: (1,2) (17,9) (23,-1) with the function f, such that e.g, f(17) = 9, and so on. Then I want to be able to change this set by replacing some pairs and have the function f reflect these changes. The only way I can see to do this in SML is to associate a variable, f_var, with f such that f_var contains the set of pairs. Modifying the set then consists of reconstructing the set and re-storing it into the variable. Is there some simpler &/or cleaner approach to this? -Dennis Heimbigner (dennis@boulder.colorado.edu)
stabl@unipas.fmi.uni-passau.de (Robert Stabl) (09/20/90)
>>>>> In article <26470@boulder.Colorado.EDU>, dennis@boulder.Colorado.EDU (Dennis Heimbigner) writes: Sorry for the long citation but it is needed for better understanding: Dennis> I have only recently begun to look at SML and I am curious Dennis> as to the best method for representing functions that are Dennis> defined by specifying a set of pairs of values, where the set contents Dennis> varies over time. This is more-or-less analogous to prolog assert/retract Dennis> or to functional data base model base functions. Dennis> For example, I want to associate the set of pairs: Dennis> (1,2) Dennis> (17,9) Dennis> (23,-1) Dennis> with the function f, such that e.g, f(17) = 9, and so on. Dennis> Then I want to be able to change this set by replacing some Dennis> pairs and have the function f reflect these changes. Dennis> The only way I can see to do this in SML is to Dennis> associate a variable, f_var, with f such that f_var Dennis> contains the set of pairs. Modifying the set then Dennis> consists of reconstructing the set and re-storing it into Dennis> the variable. This could be *one* way. But, since SML is a *functional* language, try the following (the input follows the '-', SML output the '>'), the following functions were written using "Standard ML of New Jersey, Version 0.56": - exception unbound; (* needed for undefined values *) > exception unbound - fun update f (x, y) = fn n => if (n = x) then y else f (n); > val update = fn : (''a -> 'b) -> ''a * 'b -> ''a -> 'b (* this function updates f with the new pair (x, y) *) - fun raise_unbound x = raise unbound; > val raise_unbound = fn : 'a -> 'b (* The first update uses this function *) - val f = update raise_unbound (1, 2); > val f = fn : int -> int (* the first pair *) - val f = update f (17, 9); > val f = fn : int -> int (* the next one *) - val f = update f (23, ~1); > val f = fn : int -> int (* and so on *) (* now the application of f *) - f(17); > val it = 9 : int - f(23); > val it = ~1 : int - f(3); > uncaught exception unbound Hope this helps. -- >>>>>>>>>> Robert Stabl <<<>>> stabl@unipas.fmi.uni-passau.de <<<<<<<<<<
norman@d.cs.okstate.edu (Norman Graham) (09/20/90)
From article <STABL.90Sep19204925@trillian-gw.fmi.uni-passau.de>, by stabl@unipas.fmi.uni-passau.de (Robert Stabl): > In article <26470@boulder.Colorado.EDU>, dennis@boulder.Colorado.EDU (Dennis Heimbigner) writes: >> [Omitted discussion where Dennis wants to create a function dynamically, >> by adding (or removing) input/output information to (or from) the >> function at run time.] Dennis originally asked for something analogous to Prolog's database manipulated with assert and retract. Since this is 'state', and purely functional systems are stateless, you obviously can't have it. Variables do not change their values over time; and since a named function is just a variable bound to a 'function value', that variable must represent the same function for the life of the variable. [This is very basic stuff and is provided only for the benefit of novice functional programmers.] [BTW, the charter of this newsgroup forbids discussion of imperative features found in some 'impure' functional languages. So SML references are out for now.] > [Now, Robert provides a SML example that illustrates what he thinks > Dennis wants. I've omitted some SML responses for brevity.] > > - exception unbound; (* needed for undefined values *) > > - fun update f (x, y) = fn n => if (n = x) then y else f (n); > (* this function updates f with the new pair (x, y) *) > > - fun raise_unbound x = raise unbound; > (* The first update uses this function *) > > - val f = update raise_unbound (1, 2); > (* the first pair *) > > - val f = update f (17, 9); > (* the next one *) > > - val f = update f (23, ~1); > (* and so on *) > > (* now the application of f *) > - f(17); >> val it = 9 : int > > - f(23); >> val it = ~1 : int > > - f(3); >> uncaught exception unbound The choice of names in this example may confuse some novice functional programmers. First, the function 'update' really doesn't update anything: It merely creates a new function value that is a little more defined than the function value passed to it. Second, the three 'val f = ...' expressions are not destructively updating f: Each f is a _different_ name--you might as well have called them f1, f2, and f3. The command interpreter creates a new lexical scope for each definition of f. Think of the above example as let f = update raise_unbound (1, 2) in let f = update f (17, 9) in let f = update f (23, ~1) in [f(17),f(23),f(3)] end end end I hope this clarifies things somewhat. Maybe I just misunderstood the question... Cheers, Norm -- Norman Graham <norman@a.cs.okstate.edu> {cbosgd,rutgers}!okstate!norman The opinions expressed herein do not necessarily reflect the views of the state of Oklahoma, Oklahoma State University, OSU's Department of Computer Science, or of the writer himself.
stabl@unipas.fmi.uni-passau.de (Robert Stabl) (09/21/90)
>>>>> In article <1990Sep20.074513.19190@d.cs.okstate.edu>, norman@d.cs.okstate.edu (Norman Graham) writes: [SML functions deleted] Norman> The choice of names in this example may confuse some novice functional Norman> programmers. First, the function 'update' really doesn't update Norman> anything: It merely creates a new function value that is a little more Norman> defined than the function value passed to it. Second, the three Norman> 'val f = ...' expressions are not destructively updating f: Each f Norman> is a _different_ name--you might as well have called them f1, f2, and f3. Norman is right, the function names were misleading (esp. the name f). But, I wanted to show that (higher-order) functional programming can be used to define databases, not implementing them by arrays, lists, or any other standard method. Fur further details I strongly recommend the following report: Stefan Sokolowski: "Applicative High-Order Programming, or Standard ML in the Battlefield", University of Passau, MIP-8908, February 1989. This report contains many, many examples concerning high-order functions, polymorphism, data types, implementation issues (type inference, interpretation, and compilation), structures, functors, signatures, "the art of applicative programming", and so on. The report results from an one-semester course on applicative high-order programming in 1988. -- >>>>>>>>>> Robert Stabl <<<>>> stabl@unipas.fmi.uni-passau.de <<<<<<<<<<
norman@d.cs.okstate.edu (Norman Graham) (09/22/90)
From article <STABL.90Sep20195507@trillian-gw.fmi.uni-passau.de>, by stabl@unipas.fmi.uni-passau.de (Robert Stabl): > But, I wanted to show that (higher-order) functional programming can be used > to define databases, not implementing them by arrays, lists, or any other > standard method. Right. You're example showed an important technique with which all functional programmers should be familiar: A functional (higher-order function) can be used to create a new function that is better defined than the original function. This is the same technique that denotational semanticists use to describe stores and environments. Yours, Norm -- Norman Graham <norman@a.cs.okstate.edu> {cbosgd,rutgers}!okstate!norman The opinions expressed herein do not necessarily reflect the views of the state of Oklahoma, Oklahoma State University, OSU's Department of Computer Science, or of the writer himself.
zmacx07@doc.ic.ac.uk (Simon E Spero) (09/23/90)
In article <STABL.90Sep20195507@trillian-gw.fmi.uni-passau.de> stabl@unipas.fmi.uni-passau.de (Robert Stabl) writes: > >Norman is right, the function names were misleading (esp. the name f). >But, I wanted to show that (higher-order) functional programming can be used >to define databases, not implementing them by arrays, lists, or any other >standard method. > The code in your example strongly resembles the way stores are handled in denotational semantics. Surely the chain of closures that results from this process would take up much more heap space than the standard methods, and be O(N) in time? Surely it would be better to store the data in a more efficent manner (an AVL tree, or suchlike), and to only package it up in function when one is needed ; foo tree <= let f == lambda x => look_up(tree,x) in map (f,[1,2,3] By the way, prehaps the best way of handling this problem is using a hash-table, but this is not really an option unless one is prepared to supply all values in one hit. Ever get the craving for a := ? :-( Simon -- zmacx07@uk.ac.ic.doc | sispero@cix.co.uk | ..!mcsun!ukc!slxsys!cix!sispero ------------------------------------------------------------------------------ The Poll Tax. | Saddam Hussein runs Lotus 123 on | DoC,IC,London SW7 2BZ I'm Not. Are you?| Apple Macs.| I love the smell of Sarin in the morning
dbm@alice.UUCP (David MacQueen) (09/28/90)
Standard ML does have references and assignments, and some implementations (such as Standard ML of New Jersey) have arrays with destructive array update. So it is possible to define hash tables. src/util/intmap.sml in the SML of New Jersey distribution is one such definition. Dave MacQueen macqueen@research.att.com
zmacx07@asunfs.doc.ic.ac.uk (Simon E Spero) (09/29/90)
In article <11396@alice.UUCP> dbm@alice.UUCP (David MacQueen) writes:
Standard ML does have references and assignments, and some implementations
(such as Standard ML of New Jersey) have arrays with destructive array
update. So it is possible to define hash tables. src/util/intmap.sml
in the SML of New Jersey distribution is one such definition.
Yes, but I thought we weren't supposed to talk about those sort of
perversions here, unless they guaranteed Ref. Transparency :-)
Still, this thread, and the parallel discussion in comp.lang.prolog on
declarative arrays, did put me in mind of one idea:
Since workstation screens have got bigger and bigger, with more and more
bit-planes, a lot of work has gone into producing chips which can copy and
move large blocks of contiguous memory very quickly. Has anybody ever tried
applying these BLTers to the problem of declarative arrays? After all,
the main difficulty with most schemes is that whilst they can catch most
cases where the physical array can be reused, most of them
seem to get really complex when applied to examples that weren't in
appendix A of the paper describing them :-)
If you have a fast BLTer behind the stumps, you should be able to use
a simpler algorithm, which combined with compile-time garbage collection
and a clever instruction scheduler, should make it possible to have all
copying performed in parallel with useful work.
Although copying will turn over a lot of memory, the holes in the heap
left will be precisely the right size for further generations of the same
array.
Has anybody tried this approach?
Simon
--
sispero@compulink.cix.co.uk ..!mcsun!ukc!slxsys!cix!sispero
------------------------------------------------------------------------------
The Poll Tax. | Saddam Hussein runs | +44-(0)81-500-3000
I'm Not. Are you?| Lotus 123 on Apple Macs |"Read my lips. No Nuke Tactics"otto@canon.co.uk (G. Paul Otto) (10/01/90)
In article <11396@alice.UUCP> dbm@alice.UUCP (mh8896) writes: > >Standard ML does have references and assignments, and some implementations >(such as Standard ML of New Jersey) have arrays with destructive array >update. So it is possible to define hash tables. src/util/intmap.sml >in the SML of New Jersey distribution is one such definition. > >Dave MacQueen >macqueen@research.att.com Apologies for my ignorance about ML, but I'm curious: can you define a generic hash function in ML? (i.e. a function which can take a argument of *any* type (on which equality is defined), and map it (in some plausible way) onto a range of integers.) If so, how? Paul ------------------------------------ Paul Otto, Canon Research Centre Europe Ltd., 17-20 Frederick Sanger Rd, Surrey Research Park, Guildford, Surrey, GU2 5YD, UK. NRS: otto@uk.co.canon Internet: otto%canon.co.uk UUCP: otto@canon.uucp PATH: ..!mcsun!ukc!uos-ee!canon!otto Tel: +44 483 574325 Fax: +44 483 574360
der@otter.hpl.hp.com (Dave Reynolds) (10/02/90)
> Apologies for my ignorance about ML, but I'm curious: can you define a > generic hash function in ML? (i.e. a function which can take a argument > of *any* type (on which equality is defined), and map it (in some plausible > way) onto a range of integers.) If so, how? No, there doesn't seem to be any satisfying way of doing this. There is certainly no built in hashing scheme as found in prolog, smalltalk etc. Not least amongst your problems is that there are no generic functions just polymorphic functions, not even user overloading. In pactice this is not so great a problem since you can't have inhomogeneous collections either! This means that for a given hash map you can only insert elements of the same type and only need a monomorphic hash function. In our local library we have a run time description (called a 'typeSpec') for each type we are interested in, which contains (amongst other things) a hash function. When you create an instance of a hash map you bind into the map a 'typeSpec' for the domain of the map. Then all the hash map functions are polymorphic on the domain of the map and rely on the typeSpec supplied as part of the map datastructure to provide little things like the hashing function. This works reasonably well for built in types and a few 'standard' constructed types but it is an annoying overhead to have to define a 'typeSpec' for each user type you might want to use as a map domain. All the hash mapping schemes we have experimented with in ML have suffered from the following limitations: (1) Only homogeneous collections/maps. (2) Inefficient unless you use an exposed imperative implementation. (3) Lack of general hashing function. Whilst (3) is annoying I've typically found it to be the least of my worries. Dave ------------------------------------------------------------------ Dave Reynolds | Phone: (0272) 799910 x 24165 Hewlett-Packard Laboratories | der@hplb.lb.hp.co.uk - UKnet Filton Road, Stoke Gifford | der@hplb.hpl.hp.com - Internet Bristol BS12 6QZ, ENGLAND | Dave Reynolds/HPC600/UX - HPDesk