<palomer>
OOP says that methods that deal with an object should belong to that object
<emu>
afaik, if you have objects, you have OOP =)
<emu>
there are many intelligent people who disagree with you, palomer
<palomer>
emu: encapsulation, inheritance and polymorphism
<palomer>
encapsulation is the key word here
<emu>
inheritence is not needed
<emu>
encapsulation just means you can have abstract data types
<palomer>
it's one of the three pillars of OOP
<emu>
no it's not
<palomer>
I didn't invent this stuff
<emu>
it's one of the foundations of a class-based OO system
<palomer>
encapsulation is not abstraction
<pattern_>
if encapsulation is the key, isn't ocaml's module system a form of OO?
<palomer>
it's the key word in our discussion
<pattern_>
OOP, i mean
<emu>
you see
<Smerdyakov>
palomer, your earlier statement about (2, 3).fst being "more object oriented" is clearly ridiculous, though.
<Smerdyakov>
palomer, like has been said, what you really meant was "looks more like Java and C++"
<emu>
which is my point
<palomer>
in this case it makes no difference
<emu>
java, c++, clos, smalltalk, self, simula, ... what do they all share in common that makes them OO?
<lament>
emu: simple
<lament>
they have things that are called 'objects' ;)
<emu>
! =)
<palomer>
c has objects
<lament>
s/are called/they call
<palomer>
yet it is not OO
<emu>
it has object-code =)
<palomer>
:o
<lament>
palomer: it's not? And C++ is?
<Smerdyakov>
palomer, do you have any basis for conducting this discussion besides that you read somewhere some quick sound bytes about OO programming?
<palomer>
yes! c++ can be OO
<emu>
why can't C?
<palomer>
Smerdyakov: I'll have you know I've been on Bjourn's webpage young man!
<palomer>
lemem grab some quotes
<palomer>
well C can, but it's a bitch:o
<emu>
I think your idea of OOP is very centered around C++ and Java
<palomer>
looks at scheme
<palomer>
actually scheme is a bad example..
<palomer>
cl
<palomer>
you can attach methods to symbols
<emu>
you can write your own "OOP" system in scheme or CL
<Smerdyakov>
Who cares whether something fits a buzzword or not...?
<emu>
or you can use clos
<emu>
I'm not sure what you mean by attach methods to symbols
<palomer>
bah, I'm still of the opinion that a programming language that does not offer the three OO features right off the bat is not OO, even if it has objects
<palomer>
with property lists get and put
<Smerdyakov>
palomer, who cares?
<emu>
palomer: that isn't how CL programmers work
<emu>
palomer: your knowledge of CL seems to be from the 60's
<palomer>
the fact they can
<emu>
there is no PUT in CL
<palomer>
I forget the function
<Smerdyakov>
palomer, can you please stop and explain why you are discussing this??
<palomer>
oh, I was just discussing emu's statement that any programming language with objects is OO
<emu>
I'm looking for common ground
<palomer>
though it seems it's impossible to start a discussion in here without starting a holy war
<emu>
and I didn't make that statement
<emu>
lament did
<palomer>
oh
<lament>
no, i didn't
* palomer
whacks lament
<emu>
19:27 < lament> they have things that are called 'objects' ;)
<lament>
yes
<lament>
i was sarcastic
<lament>
because i don't think half of the languages you listed are OO
<emu>
19:23 < emu> afaik, if you have objects, you have OOP =)
<emu>
note the smiley
<lament>
<emu> java, c++, clos, smalltalk, self, simula, ... what do they all share in common that makes them OO?
<emu>
you're right
<lament>
you imply that all those languages are OO
<emu>
I don't think Java, and C++ are OO
<Smerdyakov>
emu, stooooop
<emu>
hehee
<lament>
ok. with those two out, we can talk about "encapsulation, inheritance, polymorphism, runtime dispatch, message passing"
<emu>
inheritance? not really
<Kinners>
does anything good ever come from these sort of discussions? :)
<palomer>
A type of programming in which programmers define not only the data type of a data structure, but also the types of operations (functions) that can be applied to the data structure. In this way, the data structure becomes an object that includes both data and functions.
<emu>
self has delegation
<Smerdyakov>
"polymorphism" is a HORRIBLE word to use here.
<emu>
palomer: what kind of programming doesn't define operations?
<emu>
palomer: that description sounds like ML modules
<palomer>
I think the other wants to tie that in with the next sentence
<palomer>
grabbed it from webopedia
<lament>
emu: delegation works
<lament>
as long as there're language-level primitives for it
<emu>
anyway, I still think you can program in OO style without making use of inheritance
<palomer>
inheritance saves typing:o
<lament>
I think "oo style" and "oo language" are very different
<lament>
you can program in "oo style" in pretty much any language
<palomer>
exactly
<palomer>
(1,3).fst is oo style
<Smerdyakov>
"OO style" is pretty much NONEXISTENT.
<Smerdyakov>
No
<Smerdyakov>
palomer
* emu
moans
<palomer>
yes
<Smerdyakov>
That's C++ style
<emu>
palomer: that's fucking syntax, dumbass
<emu>
lets hear it for semantics, now
<Smerdyakov>
The difference between fst (1, 3) and (1, 3).fst is just one of punctuation and order!
<Smerdyakov>
Which has NOTHING to do with any programming paradigm!
<palomer>
what if you make an object that inherits from pair
<palomer>
fst might not know what to do with it
<Smerdyakov>
What does that have to do with syntax?
<palomer>
while .fst always will
<Smerdyakov>
No no no
<lament>
palomer: you're mad
<lament>
palomer: go read a book
<emu>
indeed
<emu>
make sure it doesn't have any Java in it
<Smerdyakov>
I guess palomer is hopeless.
<lament>
any book
<Smerdyakov>
There is NO DEFAULT MEANING for something.somethingelse
<Smerdyakov>
It's a haphazardly chosen syntactic artifact found in Java and C++.
<palomer>
erm, I get your point
<emu>
it sorta kinda imitates the smalltalk message passing paradigm
<emu>
and the syntax kidna sorta imitates the C struct shit
<palomer>
ok, then I retract what I had previously said and I rephrase it by saying that it's oo style to have the functions that deal with a data structure part of that data structure
<emu>
so
<emu>
struct foo { int data; int frob (int); }
* emu
cooks up pseudoC
<palomer>
that works
<emu>
that's so dumb
<emu>
lets see
<emu>
you need a copy of the function or a pointer to the function for EVERY SINGLE INSTANCE
<palomer>
in C
<palomer>
in c++ and java you can make it static
* emu
moans
* Riastradh
groans.
<emu>
which basically just turns it into a namespacing deal
<emu>
how about this:
<Riastradh>
palomer, you have absolutely -NO- clue what you're talking about. Quoting Bjarne Stroustroup about 'object-oriented' is just like quoting Bill Gates about how to be a good and honest person.
<steele>
there should be one dp-table per class and _not_ per instance, even in C++/Java
<palomer>
geez, last time I start a discussion in #ocaml
<palomer>
steele shut up you don't know anything, stop quoting famous people
<emu>
you can structure your data all you want
<Smerdyakov>
Good. Go back to Javaland!!! HAHA
<emu>
and then write some functions to deal with it
<palomer>
I don't like java, neither c++
<steele>
palomer: who did i quote?
<palomer>
steele: I was proving a point
* palomer
hugs steele
<Riastradh>
steele didn't quote anyone and made a perfectly valid argument.
<palomer>
I took steele's name as an example of how NOT to take part in a discussion
<Riastradh>
You quoted a moron and made no perfectly valid arguments.
<emu>
how about viewing things like this:
<lament>
instead of this discussion
<palomer>
I could have just as well used emu's name
<emu>
``putting methods into a class''
<lament>
let's just stab each other in the face
<emu>
really means
* Riastradh
stabs lament.
<emu>
the first argument of every method should be an object of that class
* lament
stabs palomer
<emu>
(every method in that class)
<Riastradh>
I wanted a chance to argue here, but I guess I came in too late and ended up just getting to the end and the burnt scraps of it.
<palomer>
emu: it says much more! in languages like ruby you can get all the methods that belong to a class and store them in an array
<emu>
so class Foo { void frob () { .. } }; really boils down to having frob be a function of one argument of class Foo
* Smerdyakov
encapsulates palomer.
<emu>
palomer: wha, so you keep track of things? so what?
<palomer>
emu: and it also entails that all classes that inherit from it also get that method
<emu>
so you can keep track of all functions which accept an object of class Foo as first argument
<lament>
palomer: so?
<lament>
that's reflection
<palomer>
hrm, you have a point...
<emu>
palomer: as for inheritance
<emu>
it's the subclass relationship
<emu>
if Bar is a subclass of Foo, presumably a function which accepts Foo can also accept Bar
<Riastradh>
Inheritance is just searching up a tree of classes for a method and applying it just the same.
<palomer>
I guess it just makes sense that methods should belong to the objects they deal with in OO, like having no side-effects in FP
<emu>
no
<Riastradh>
Er, applying it in just the same manner.
<Riastradh>
No, methods definitely don't have to 'belong' to an object.
<lament>
palomer: no.
<emu>
having no side-effects in FP is not ``just a feeling''
<lament>
palomer: contrexample: any multiple dispatch object system
<Riastradh>
If they belong to an 'object' that's bad design, if it's an object system in which classes are used.
<lament>
*counterexample
<emu>
lament: heh, I was just about to bring that up
<Smerdyakov>
All right. Time for some emergency positive vibes.
<Riastradh>
As lament pointed out, there are object systems in which methods are associated with generic functions and not objects or classes.
<lament>
Smerdyakov: that's not a boy!
<Riastradh>
Actually, it doesn't necessarily have to support multiple dispatch, anyways: it could be a single dispatch, generic function-based object system.
<Riastradh>
Like that of RScheme.
<palomer>
hrm, having a discussion without formal definitions gets a little tricky
<emu>
or (send object message args...)
<Riastradh>
'Object-oriented' has no formal definitions: it is too vague and there are too many variants of it that it's impossible to define.
<emu>
or object message: arg message: arg message: arg
<emu>
or generic-function arg1 arg2 arg3
<emu>
woo
<palomer>
so we'll leave it at that: discussions on OO are useless
<Smerdyakov>
The formal definition of "object oriented" is "an excuse for people to write books about 'design patterns.'"
<emu>
indeed
<Smerdyakov>
palomer, and OO is useless!
<Riastradh>
And to say that '("foo", "bar").fst' is silly.
<palomer>
computers are useless!
<Riastradh>
Er, that that's object-oriented.
<emu>
it's silly too
<lament>
Smerdyakov: no, oo isn't useless.
<Smerdyakov>
lament, my daddy could whoop your daddy
<Riastradh>
Of the definitions of 'object-oriented,' there are plenty of useful ones.
* emu
thinks that obfuscation-oriented programming is well-defined enough...
<lament>
Smerdyakov: my mom could whoop your mom!!!
<palomer>
this is why mathematics is so nice, a given statement is either true or false
<emu>
ahahahaha
* emu
introduces palomer to constructive logic
<lament>
palomer: "this sentence is false"
<emu>
self-reference is a killer
<lament>
palomer: this is why the internet is so nice, you can say stuff AND NOT GET YOUR ASS KICKED
* Riastradh
kicks lament's ass.
* emu
institutes the law of the excluded lament
<lament>
Riastradh: not fair!
<palomer>
yes, I have nightmares where I have discussions about OO with my fellow class mates and then I get stabbed in the face
<lament>
emu: yes, self-reference is a killer
<mrvn>
/kick lament
<lament>
emu: also, it's a requirement for turing-completeness :)
<mrvn>
lament: we know your ip. :)
<lament>
emu: or, at least, is always present in turing-complete systems
<lament>
mrvn: oh, really? So that "YOUR COMPUTER IS CONSTANTLY BROADCASTING AN IP ADDRESS" spam was true?!
<emu>
interlegchewall property
<mrvn>
lament: yes, realy scary.
<lament>
hehe
<mrvn>
But hey, for only 99.99$ per monthz you can install this great software that blocks him from doing so.
<mrvn>
lament: Why woul self reference be required for turing comp0letness?
<lament>
mrvn: it isn't required
<lament>
mrvn: it follows.
<mrvn>
Ocaml doesn't have self references for classes.
<lament>
that's not what i mean. I don't mean language-level stuff.
<emu>
the partial recursive functions correspond to turing-machine computable ones
<palomer>
if turing completeness => self reference then ocaml => no self reference => not turing complete then assembly > ocaml qed
<mrvn>
palomer: the oo subset at least
<emu>
no real computer language is turing complete because we don't have infinite memory/disk =)
<lament>
palomer: nngah
* emu
ducks
<lament>
palomer: you can write a quine in ocaml
<palomer>
quine?
<lament>
palomer: a program that prints its own source code
<lament>
palomer: do you know why i know that you can do that?
<mrvn>
emu: give me a turing maschine and I will build you a ocaml runtime that is turing complete. :)
<emu>
I prefer programs which print the source code to top-secret programs
<lament>
palomer: because ocaml is turing complete, and quines can be written in all turing-complete languages
<emu>
mrvn: sorry, I seem to be all out of them
<mrvn>
lament: Thats what youmean by self reference?
<emu>
I also prefer programs which print the source code to homework-assignments
<emu>
and work
<lament>
mrvn: yes - it's enough self-reference to cause weird stuff to happen
<mrvn>
Do you guys know the shortest C programm that prints out its own source?
<lament>
mrvn: for example, see the halting theorem
<emu>
halting problem, maybe
<emu>
the halting problem is that you cannot stop a flamewar once it has started
<lament>
halting theorem says that the halting problem can't be solved.
<palomer>
wait, why is a quine so hard to do?
<Smerdyakov>
mrvn, I DO!
<lament>
its proof is disturbing, and relies on self-reference aka quines
<palomer>
find position where I start, position where I end, print from start to end
<mrvn>
palomer: I is realy easy. Takes 0 bytes of C source :)
<lament>
palomer: it isn't
<emu>
huh
<emu>
the proof that you can't solve the halting problem is not that disturbing
<lament>
palomer: huh?
<palomer>
my book proves the halting problem with C
<palomer>
C!
<mrvn>
palomer: it can't
rox|heimdienst is now known as rox
<lament>
holy shit
<palomer>
<lament> palomer: a program that prints its own source code
<lament>
palomer: have you ever considered learning the basics of computer science?
<lament>
it's a very interesting subject.
<emu>
Learn Computer Science in 21 Days!
<palomer>
heh
<palomer>
I'm going to take theory of computation next semester
<Kinners>
I prefer Learn Computer Science in 20 Days!
<palomer>
I love that stuff
<emu>
``Be a star HTML, JAVA, XML, VB++.NET programmer in 21 days''~
<emu>
!
<Smerdyakov>
Oh, we have a greeeeat Theory of Computation class here.
<palomer>
which university?
<Smerdyakov>
CMU
<Smerdyakov>
The class is really pathetic and makes me want to HURL.
<emu>
colorado mining university
<palomer>
so cmu sucks?
<emu>
completely moronic univ
<palomer>
why does the class suck?
<emu>
Smerdyakov: which #?
<emu>
151?
<lament>
Learn computer science in a countable infinity of progressively smaller time units!
<Smerdyakov>
453
<emu>
er
<Smerdyakov>
It sucks because it's too easy, like every other class here.
<Smerdyakov>
Next question? =P
<emu>
ah
<lament>
Learn computer science in less time it'll take you to forget it!
<palomer>
what do you guys cover in the first theorectical computer science course?
<emu>
in theory, you type on a computer and it works
<emu>
in practice, demons fly out of your nose
<palomer>
only if you use vi
<emu>
or C
<palomer>
god is gentler to us emacs users
<Smerdyakov>
palomer, everyone does everything the same way everywhere.
<emu>
if you use vi, bill joy flies out of your nose
<emu>
hurts a lot more
<palomer>
Smerdyakov: not in my school, we never got to turing machines:/
<palomer>
oh, and our intro. to algorithm class SUCKS
<emu>
turing machines are the most annoying way to represent computability
<palomer>
it's so bad it's not funny
<Smerdyakov>
palomer, yeah, your school sucks. Haha
<palomer>
it does:(
<lament>
turing machines are stupid, ugly and horribly overhyped
<Smerdyakov>
Theory of anything is horribly overhyped
<palomer>
yhea, the real computational model is the abacus
<emu>
the only nice thing about them is that they kinda sorta could be conceivably built out of mechanical parts
<emu>
writing turing-machine programs is an exercise in torture
<palomer>
I find it fun
<emu>
you even have to come up with your own calling-conventions
<emu>
ack
<palomer>
I'm taking a course that's covering NP completeness, so I have 2 weeks to learn turing machines
<palomer>
with a horrible horrible book
<palomer>
anyone heard of hopcroft?
<lament>
brainfuck is neater, simpler and generally more fun, while being somewhat similar.
<lament>
(to turing machines)
<lament>
lambda calculus is beautiful and damn cool. Also, it was invented _before_ turing machines.
<emu>
does anyone have any idea how coffee-drip machines are supposed to be cleaned?
<mrvn>
palomer: implement a turing machine in ocaml.
<emu>
implement a turing machine with a turing machine!
<lament>
implement ocaml on a turing machine
<emu>
implement ocaml on a turing machine implemented in perl implemented in java implemented in brainfuck implemented in malbolge
<palomer>
mrvn: no!
<mrvn>
You can implement a turing maschine with a few lines of ocaml code. The compiler does all the work for you.
<lament>
i'm afraid malbolge is not turing-complete.
<palomer>
lament: no!
<palomer>
emu: no!
<emu>
lament: i thought no one dared to try and prove it?
<mrvn>
whats balbolge?
<emu>
malbolge is the language so evil that no one has written a "Hello World" program in it
<emu>
though they did manage to write a "HELlo wORlD" program in it
<lament>
emu: no. but most people think it's not.
<emu>
I think the program was evolved until they got it that far
<lament>
afaik the most complicated malbolge program to date is the 'yes' clone
<lament>
it actually has a loop!
<emu>
wow
<emu>
how many computation-millenia did that take to work out?
<lament>
heh
<Smerdyakov>
Why, why, why discuss such stupid things?
<mrvn>
Users are encouraged to make their own, unique homebrew versions of Malbolge and Dis, in order to achieve the kind of portability problems normally associated with major languages;
<mrvn>
rofl
<lament>
mrvn: not only that; the implementation provided on the malbolge home page isn't standard-compliant.
<mrvn>
other solutions can be found with different parameters: "hello World" is found after searching 28,300 nodes if the beam width is 1,000 (reward still 10), but has more memory accesses (71).
<mrvn>
That could be something for the next pfc :)
<whee>
haha
<mrvn>
Write a malbolge program that outputs your email address or a programm producing such.
<whee>
that pfc would be followed by a bunch of people whining
<mrvn>
The later would all be started simultanious and the first to output the email wins :)
<mrvn>
I'm still looking for some spcs on malbolge
<mrvn>
type stone = Empty | Block | X_block | O_block
<mrvn>
but both with `X and `O
<Riastradh>
What does `Blah do?
<mrvn>
I have a few places where I have to convert one into another and I though polymorphics variance would do that for me.
<mrvn>
Blah?
<Riastradh>
i.e., does the backtick do anything special?
<whee>
it denotes a polymorphic variant
<Riastradh>
Which is...?
<mrvn>
type player = [ `O | `X]
<mrvn>
type stone = [ `X | `O | `Empty | `Block ]
<Riastradh>
What does it do, though?
<mrvn>
let player = `X;;
<mrvn>
let bla = function `X -> 0 | `O -> 1;;
<mrvn>
val bla : [< `O | `X] -> int = <fun>
<mrvn>
let foo = function `X -> 0 | `O -> 1 | `Block -> 2 | `Empty -> 3;;
<mrvn>
val foo : [< `Block | `Empty | `O | `X] -> int = <fun>
<mrvn>
foo player;;
<mrvn>
bla player;;
<mrvn>
foo and bla have different types but both accept player.
<mrvn>
I think i will use polymorphic variants.
<mrvn>
just for fun
<whee>
heh
<whee>
that pfc is over, isnt it?
<mrvn>
yes.
<palomer>
hrm, I wonder if there are things a turing machine can't solve but yet are computable
<pattern_>
practically speaking, of course
<mrvn>
Since computable is everything a turing machine can compute, NO
<pattern_>
because your classic turing machine might not be efficient enough to do it within the lifetime of the universe, say
<pattern_>
like, maybe it can't compute the precise value of pi ;)
palomer has quit [Remote closed the connection]
<mrvn>
pattern_: the time taken is irelevant
<mrvn>
theoretically speaking
<mrvn>
:-P
<mrvn>
I'm sure there are algorithms that take O(n) in C but take O(n^2) on a turing machine.
<pattern_>
"An American engineering team brings a prototype to a French engineering team. The French team's response is: 'Well, it works fine in practice; but how will it hold up in theory?'"
<mrvn>
I don't think you can get from O(n^k) to O(k^n), i.e. leaving the complexity class.
Kinners has left #ocaml []
<mrvn>
pattern_: The Vulcan science council has ruled time travell as impossible. So this guy here from the 25th century clearly can't be from the future.
<pattern_>
hehe
lament has quit ["Did you know that God's name is ERIS, and that He is a girl?"]
mattam has quit ["leaving"]
Riastradh has quit [Read error: 60 (Operation timed out)]
palomer has joined #ocaml
palomer has quit [leguin.freenode.net irc.freenode.net]
Sonarman has quit [leguin.freenode.net irc.freenode.net]
liyang has quit [leguin.freenode.net irc.freenode.net]
emu has quit [leguin.freenode.net irc.freenode.net]
smkl has quit [leguin.freenode.net irc.freenode.net]
skylan has quit [leguin.freenode.net irc.freenode.net]
emu has joined #ocaml
Sonarman has joined #ocaml
palomer has joined #ocaml
liyang has joined #ocaml
smkl has joined #ocaml
skylan has joined #ocaml
liyang_ has joined #ocaml
smkl has quit [Remote closed the connection]
smkl has joined #ocaml
liyang has quit [Read error: 104 (Connection reset by peer)]
pattern_ has quit ["..."]
<palomer>
let dfs = fun v g ->
<palomer>
let rec dfs_rec = fun seen vls -> match vls with
<palomer>
[] -> []
<palomer>
| h::t when List.mem h seen -> dfs_rec seen t
<async>
i have this header type{} that must be included in several other more complex types.. but the header name can't be the same in all of the complex types.. should I just name all the headers differently? or is there a better solution?
<mrvn>
palomer: shouldn't that be (has_edges_from h g)?
<mrvn>
async: what?
<async>
ok like i have type header = { id: int; name: string }
<mrvn>
and then?
<async>
and then i have type attr_header = { head: header; other_crap_in_this header }
<async>
and then i have type mode_header = {head: header; other_crap }
<async>
i have like 20 of those
<async>
but they all need the header in them
<mrvn>
the head will shadow the previous one.
<async>
yeah it won't let me do that unless i name them differently
<mrvn>
You can name them differently, make an accessor (with different names each) or uses classes.
<mrvn>
Or put each bla_header in its own module.
<async>
alright let me look up all that you said ;)
<async>
thanks
<mrvn>
Classes is probably best because then you can pass a attr_header to a function taking a header
<async>
hehe i
<async>
i have this spite towards classes.. because i ditched c++.. but i guess they are better in ocaml
<palomer>
classes aren't so bad in c++
<palomer>
they allow functors
<mrvn>
class header id name =
<mrvn>
object
<mrvn>
method id : int = id
<mrvn>
method name : string = name
<mrvn>
end
<mrvn>
class attr_header id name other =
<mrvn>
object
<mrvn>
inherit header id name
<mrvn>
method other : float = other
<mrvn>
end
<mrvn>
let attr = new attr_header 1 "attr" 2.;;
<mrvn>
attr#name;;
<mrvn>
# - : string = "attr"
<palomer>
:o
<async>
very cool/interesting
<palomer>
whew, I looked at quicksort from the oreilly book
<palomer>
quite long...
<async>
in c? or ocaml?
<palomer>
thought it would be like the quicksort in haskell
<mrvn>
there is an algorithm for transforming one into the other.
<mrvn>
Its pretty simple to convert for/while loops into recursions.
<mrvn>
Its a bit more tricky to convert recursion into tail recursion
<palomer>
is it doable?
<mrvn>
Sure.
<palomer>
theres an algorithm to transform all recursions into iterations?
<mrvn>
In general you convert from a normal program into CPS (continuation passing style). Thats all tail recursive.
<palomer>
ohmy.
<palomer>
so fold_right is tail recursive!
<palomer>
I knew it!
<mrvn>
let rec fac i = if i = 0 then 1 else i * (fac (i-1));;
<mrvn>
palomer: no, fold_right is not but can be transformed into.
<mrvn>
You probably know the recursive fac function?
<palomer>
tail recursive?
<palomer>
of course
<palomer>
it's quite elegant
<mrvn>
let fac i =
<mrvn>
let rec fac i cont =
<mrvn>
if i = 0
<mrvn>
then cont 1
<mrvn>
else fac (i-1) (fun x -> i*x)
<mrvn>
in
<mrvn>
fac i (fun x -> x);;
<mrvn>
That would be tail recursive
<palomer>
cont 1?
<mrvn>
cont is a function
<palomer>
ah
<palomer>
so the same would apply for summation
<palomer>
gotcha
<mrvn>
ahh, bug:
<mrvn>
let fac i =
<mrvn>
let rec fac i cont =
<mrvn>
if i = 0
<mrvn>
then cont 1
<mrvn>
else fac (i-1) (fun x -> cont (i*x))
<mrvn>
in
<mrvn>
fac i (fun x -> x);;
<palomer>
but if a function can be made to be tail recursive, whats the harm in using it?
<mrvn>
palomer: its not realy tail recursive.
<palomer>
like using fold_right and fold_right?
<palomer>
it's made to be tail recursive!
<mrvn>
You create a new cont function with each recursion
<mrvn>
It doesn't need stack space but now it needs heap space.
<palomer>
ah
<mrvn>
Doing a manual conversion to a tail-recursiv form is way more efficient if possible.
<mrvn>
let fac i =
<mrvn>
let rec fac i accu =
<mrvn>
if i = 0
<mrvn>
then accu
<mrvn>
else fac (i-1) (i * accu)
<mrvn>
in
<mrvn>
fac i 1;;
<palomer>
let rec fac i = 1-> 1 | n -> i * n;;
<palomer>
whats wrong with that?
<mrvn>
where is the recursion?
<palomer>
erm, woops
mattam has joined #ocaml
<palomer>
let rec fac i = 1 -> 1 | n -> n * fac (n-1);;
<mrvn>
Syntax error
<palomer>
let rec fac =fun i -> match i with
<palomer>
| 1 -> 1
<palomer>
| x -> x * fac (x-1);;
<palomer>
works
<palomer>
it's also tail recursive
<pattern_>
mrvn, i don't understand what the "cont" and "accu" functions in your examples above are for
<mrvn>
cont is the continuation to call next.
<mrvn>
Accu is the accumulator for our result.
<mrvn>
Do you know this function?
<mrvn>
let rec binomi = function
<mrvn>
0 -> 0
<mrvn>
| 1 -> 1
<mrvn>
| n -> (binomi (n-1)) + (binomi (n-2));;
<pattern_>
what do you mean by continuation? and what is "call next"?
<Kinners>
palomer: why do you think it is tail recursive?
<mrvn>
pattern_: Its called continuation because thats where we continue when the function is done.
<pattern_>
i see
<palomer>
Kinners: because the paremeters of the function are no lenger needed after the recursive function call
<pattern_>
mrvn, makes perfect sense :)
<pattern_>
now, why will you continue to "accu" when you use it in your calculation: (i * accu) ?
<palomer>
im off te bed
<palomer>
night
<pattern_>
oh, it's the accumulator
<Kinners>
palomer: it creates a stack of n * (n-1) * (n-2) * (n-3) * etc. doesn't it?
<mrvn>
CPS is realy fun. :)
<mrvn>
let binomi n =
<mrvn>
let rec binomi cont = function
<mrvn>
0 -> cont 0
<mrvn>
| 1 -> cont 1
<mrvn>
| n -> (binomi (fun x -> binomi (fun y -> cont (x+y)) (n-2)) (n-1))
<mrvn>
in
<mrvn>
binomi (fun x -> x) n;;
<mrvn>
Try that in fortran or C
<pattern_>
what does "cps" mean?
<mrvn>
Continuation passing Style
<pattern_>
ahh
<pattern_>
so what do the "cont" and "accu" functions do exactly?
<pattern_>
i'm still pretty lost
<mrvn>
pattern_: accu is just an int to gather the result.
<Kinners>
pattern_: do you understand why palomer's example isn't tail recursive?
<pattern_>
oh, damn... i was thinking it was a function, not a value :P
<mrvn>
cont is a function that gets called (tail-recursively) with the result of this recursion.
<pattern_>
kinners, no i don't understand... i thought tail recursion was when the last stpe in your function is a recursive call... so isn't that what palomer has?
<pattern_>
mrvn, but what does that function _do_ with it's argument?
<mrvn>
pattern_: whatever would need to be done in the non tail-recursive function.
<pattern_>
ahh!
<Kinners>
pattern_: with x * fac (x-1), when is the multiplication actually done?
<pattern_>
ok, so that was an example of how to convert a non-tail recursive function to a tail recursive one... i hadn't caught that connection
<pattern_>
kinners, you got me :)
<pattern_>
i don't know anything of order of evaluation in ocaml
<pattern_>
the tutorials i read didn't cover it :(
<pattern_>
i would guess the multiplication is done last
<Kinners>
pattern_: what I'm trying to (badly) say is, the multiplication relies on the result of the fac call
<pattern_>
yes, definately
<pattern_>
or, i mean, yes, i see what you're saying
<pattern_>
so if the multiplication relies on the factorial, then palomer's function can't be tail-recursive
<Kinners>
right, you start multiplying once you've stopped recursing and return the 1
<pattern_>
ok, i see now
<Kinners>
if you enter that function into ocaml, #trace faq;; fac 10;; you can see how it works
<pattern_>
so the "last" in a tail recursive function doesn't mean "last" syntactically, but "last" as far as execution goes
<pattern_>
it's the syntax that got me thinking it was tail recursive
<pattern_>
kinners, i will try that
<pattern_>
i've never used trace
<pattern_>
neat!
<pattern_>
so that shows what value the fac function has at each step?
<Kinners>
the left pointing arrow is the value passed to fac, right pointing is the result
<pattern_>
thanks, i was just going to ask about the arrows :)
<pattern_>
<mrvn> let fac i =
<pattern_>
<mrvn> let rec fac i cont =
<pattern_>
<mrvn> if i = 0
<pattern_>
<mrvn> then cont 1
<pattern_>
<mrvn> else fac (i-1) (fun x -> i*x)
<pattern_>
<mrvn> in
<pattern_>
<mrvn> fac i (fun x -> x);;
<pattern_>
<mrvn> cont is a function that gets called (tail-recursively) with the result of this recursion [to do] whatever would need to be done in the non tail-recursive function
<pattern_>
so what is it, precisely that we would need to get done to make this equivalent to the non-tail recursive function, which i presume is: <mrvn> let rec fac i = if i = 0 then 1 else i * (fac (i-1));;
<pattern_>
i mean, what should cont be to make the two functions equivalent?
<mrvn>
pattern_: The firt is the result of transforming hte later into CPS.
<pattern_>
(sorry i'm slow on the pickup here)
<pattern_>
mrvn, yes, i understand the purpose of the first.. but i'm having problems with the cont
<pattern_>
i want to figure out how this works :)
<Kinners>
pattern_: you know about the accu example?
<pattern_>
kinners, i have seen the accu example, don't think i understand it yet
<pattern_>
let me look again...
<mrvn>
pattern_: I need to calculate fac 5. I know thats 5*fac(4)
<mrvn>
Now I don#t want to call fac(4), wait for it to return and then multiply.
<Kinners>
pattern_: basically instead of using the stack to store intermediate results, you calculate and pass them yourself
<mrvn>
Instead I call fac(4) and tell it to multiply the result by 5
<mrvn>
fac 4 (fun x -> 5*x)
<pattern_>
hmm... that's something else i'm confused about: (fun x -> 5*x) where does it get x from? should this anonymous function's arguments be to it's right? like so: (fun x -> 5*x) (fac 4) ?
Sonarman has quit ["leaving"]
<mrvn>
No, fac n cont will call cont with some number.
<mrvn>
Its "fac 4"'s job to call the function with 24.
<mrvn>
The recurion ends with "0 -> cont 1"
<mrvn>
the 1 will be the x for the anonymous function from fac 1
<pattern_>
so i can use the syntax: "y myfunction" to call myfunction with y as an argument?
<mrvn>
pattern_: no.
<pattern_>
then why doe "fac 4 (fun x -> 5*x)" call the anonymous function with an argument of 4? what am i missing?
<pattern_>
s/doe/does
<mrvn>
pattern_: it doesn't, it calls it with 24
<pattern_>
i mean with 24
<pattern_>
:P
<mrvn>
fac 4 (fun x -> 5*x) becomes fac 3 (fun x -> (fun x -> 5*x) 4*x)
<mrvn>
fac 2 (fun x-> (fun x -> (fun x-> 5*x) 4*x) 3*x)
<pattern_>
aaahh!
<mrvn>
fac 1 (fun x -> (fun x-> (fun x -> (fun x-> 5*x) 4*x) 3*x) 2*x)
<mrvn>
fac 0 (fun x -> (fun x -> (fun x-> (fun x -> (fun x-> 5*x) 4*x) 3*x) 2*x) 1*x)
<mrvn>
(fun x -> (fun x -> (fun x-> (fun x -> (fun x-> 5*x) 4*x) 3*x) 2*x) 1*x) 1
<mrvn>
(fun x -> (fun x-> (fun x -> (fun x-> 5*x) 4*x) 3*x) 2*x) 1
<pattern_>
it will take me a bit to understand all that :)
<mrvn>
3 forms of binomi
<pattern_>
so, one quick question
<mrvn>
recurive, CPS, and tail-recursive (iterative)
<pattern_>
how does ocaml know to pass (fun x -> 5*x) as an argument, and not just evaluate it?
<mrvn>
pattern_: What should x be?
<pattern_>
i guess there isn't one, so it's unambiguous
<mrvn>
(function x -> y) is evaluated if it gets passed an x.
<pattern_>
what if i wanted to pass another arugment to fac 4, after (fun x -> 5*x)
<mrvn>
pattern_: then you just do.
<pattern_>
i love ocaml, btw... it has wacky syntax, and is one of the hardest things i've tried to learn, but when things like this crystalize and i glimpse some of its power its really great :) i'm having tons of fun
<mrvn>
Many compiler use CPS transformation because that has only and allways tail-recursion which then translate into simple jmp instructions.
<pattern_>
you just do what? pass it another function without an argument? ocaml will recognize that say: "fac 4 (fun x -> 5*x) (fun x -> 5*x)" the 2nd "fun x" has no argument, so it shouldn't be evaluated, but how does it know that the first "fun x" shouldn't be passed the 2nd "fun x" as an argument instead of not evaluating either and passing them both to fac 4 ?
<mrvn>
pattern_: look atthe binomi example.
<pattern_>
ok
<pattern_>
will do... but it'll take a bit for me to understand it, so i'll bbl
<mrvn>
bin(n)=bin(n-1)+bin(n-2), so you have two functions.
<pattern_>
i'm not sure i see the connection
<pattern_>
those are two seperate recursive calls to bin
<pattern_>
what does that have to do with our fac 4 (fun x) (fun x) example?
<mrvn>
pattern_: The bin(n-1) gets passed the bin(n-2) and the + function
<pattern_>
oh
<mrvn>
Thus two fun x -> ... in there.
<mrvn>
fun x and funy actually.
<pattern_>
but bin(n-2) only takes one argument, doesn't it? it takes "n"
<mrvn>
pattern_: two, cont and n
<mrvn>
The trick is to create an anonymous function that calls the two functions you want to pass and pass that instead.
<pattern_>
so bin(n-1) gets passed + as n, and bin(n-2) as cont?
<mrvn>
no, n-1 as n and a function calculating x+bin(n-2)
<mrvn>
as cont
<pattern_>
oh, right
<pattern_>
very interesting
<emu>
fun fun fun
<pattern_>
i guess it's kind of starting to make sense
<pattern_>
yes! super fun, emu!
<pattern_>
you definately don't get to have this much fun in c or perl
<mrvn>
Ever implemented a game where you do a minimax search or something?
<pattern_>
(sorry to mention those unmentionables in here)
<emu>
ction
<pattern_>
i actually haven't, mrvn... i'm self-taught as far as computer stuff goes, so my education is sorely lacking
<emu>
miniminiminimax is easy and useful way to do gamesearch
<pattern_>
i've heard of it... and someone explained what it was to me once, but i forgot
<mrvn>
In games you often want to do a lot of calculation to plan ahead. But you can't sit there for two hours and think.
<emu>
well you could..
<emu>
i thikn most ppl would get annoyed though
<mrvn>
the user would get anoyed.
<pattern_>
:)
<mrvn>
So what you do is you transform the thinking into CPS. During the evaluation you check for the elapsed time and every so often you don't call the continuation but you call the gui first.
<mrvn>
Update a progress bar or do some moves you already decided to make.
<emu>
CPS is really funky
<mrvn>
Or you can Marshall the continuation to disk and quit. The next time you start you Marshal the continuation back in and call it.
<mrvn>
It will just continue where it left of.
<pattern_>
wow
<pattern_>
i bet a whole lot of os stuff would be so much easier to write in ocaml
<mrvn>
And that is realy neat.
<mrvn>
pattern_: OS stuff usually doesn't work well with garbage collection
<emu>
well
<emu>
that's not really a problem
<emu>
(a) it's been done before (b) GC can co-exist with other forms of memory management
<mrvn>
low level stuff hat is.
<pattern_>
actually, i saw some threads that said that even garbage collectors have been written with garbage collected languages, and they work great
<emu>
T's GC was written in T
<mrvn>
pattern_: GCs can be written to use no extra memory.
<mrvn>
(apart from a fixed static amount).
<mrvn>
If you don't allocate or free memory in the GC itself it doesn't matter what its written in.
<pattern_>
anyway, doesn't ocaml allow you to tweak it's garbage collection somehow? so that you could tell it to clean up at more opportune moments?
<pattern_>
(not that i really have a need to know on this subject... as i'm far from doing anything that advanced with ocaml)
<mrvn>
pattern_: Gc.compackt e.g.
<emu>
there are systems that do have that
<emu>
it's not inconceivable
<mrvn>
Its also realy easy to do.
<pattern_>
so if you can do that, then what other issues do you have with gc and low-level os development?
<mrvn>
pattern_: Some things have to be fine tuned. I can't have the GC running while I need to put samples into the DSP.
<emu>
real-time GC
<emu>
incremental
<mrvn>
And catching all such places and disabling the GC for that time is a pain.
<pattern_>
mrvn, right... that's why i asked about whether you could control when the gc collects
<emu>
mrvn: why?
<mrvn>
Just imagine you forget to turn the GC back on just once.
<emu>
sigh
<emu>
that's why you don't explicitly do it
<emu>
in ocaml you don't really have macros so much
<emu>
but you can do (shut_gc_off (fun ... ))
<pattern_>
well, forgetting to turn the GC back on would be the same as having a buggy program in a non-GC language
<emu>
then it's shut_gc_off's responsibility
<mrvn>
You also want some things to realy die, even if the GC would say they are alive.
<emu>
but if the GC says they are alive
<emu>
then that means someone has a reference
<mrvn>
you have dangling pointers
<mrvn>
and most likely a bug
<emu>
dangling pointers isn't the phrase
<emu>
you mean stray references
<mrvn>
But its no use that you leak memory and start swapping.
<emu>
you can't technically leak memory in a GC'd system unless the GC is buggy
<emu>
you can maintain stray/unnecessary references
<emu>
this can be weeded out with the appropriate GC inspection tools
<mrvn>
yes, it would be your fault for keeping stuff alive too long. But sometimes its better to get a stry reference than swap.
<emu>
no, that's a C compromise
<emu>
and I think you meant dangling pointer there
<mrvn>
The core part should be only a few K and a lot of that asm anyway. In a mikrokernel there is hardly anything to do in the core that would need or benefit from a GC.
<mrvn>
Once the core is there you can use GC and all.
<emu>
why speculate when you can read history...
<pattern_>
well, that would still leave lots of fun stuff for ocaml to do
<mrvn>
pattern_: sure.
<mrvn>
pattern_: all the FS stuff especially.
<emu>
I think the biggest problem will be squeezing that damn camel into a computer
<pattern_>
i was thinking that the continuations would be great for a suspend feature
<mrvn>
A filesystem with automatic defragmentation and compaction would be wonderfull.
<mrvn>
emu: nah, just buy a big enough scanner or a mall enough caml.
<emu>
pattern_: well, that's what pre-emptive multi-processing does
<emu>
pattern_: forcibly takes the continuation and stops the process
<emu>
hehe
<pattern_>
ahh
<pattern_>
but they usually do it with c
<pattern_>
:(
<mrvn>
pattern_: continuations can be used for callcc, suspend, multithread,...
<emu>
CPS requires a level of cooperation, however
<pattern_>
yes, definately
<mrvn>
emu: You can set a timer that changes the current continuation
<emu>
CPS, not pre-emptive
<mrvn>
You would loose all the work of the currently running continuation though.
<mrvn>
It would have to start again when the thread is next woken up
<emu>
what's the currently running continuation?
<emu>
hehe
<emu>
if it's running, it's not a continuation =)
<pattern_>
good point :)
<mrvn>
emu: you would need a special register or reference for it.
<emu>
I think on Intel it's called IP
<emu>
CS:IP
<mrvn>
emu: But since cps code is usually compiler generated thats trivial.
<emu>
EIP
<mrvn>
emu: No, it would be the first parameter in the current stackframe or something.
Kinners has quit [Read error: 104 (Connection reset by peer)]
<emu>
yea yea
<pattern_>
ok, this is all fun guys, but i'm going to go and try to learn more ocaml by try to study the code you pasted eaarlier :)
<emu>
that's already the case, you know
<emu>
almost all calling conventions wokr that way
<emu>
push ret-address, branch
<emu>
push cont-address, branch
<emu>
same thing
<mrvn>
emu: usually you don't have a fixed first (or last) parameter thats a continuation.
<emu>
i just said you do
<emu>
hehe
<mrvn>
x86 cpus use the stack for the return address, alpha uses R26 per convention.
<emu>
it's implicit in the calling conventions
<emu>
well cross-arch who cares? portability is its own issue
<emu>
we're not calling from x86 to alpha
<mrvn>
But the return addres is something else than a continuation
<emu>
SMP, asymmetric processors!
<emu>
why is it?
<emu>
you know what the RETURN instruction does?
<emu>
pop address, branch to it
<emu>
hehe
<mrvn>
emu: there is no return on alpha :)
<emu>
so?
<emu>
they do the equivalent
<mrvn>
alpha only has JMP
<emu>
pop address, branch to it
<emu>
didn't I just say this?
<emu>
didn't I just say that RETURN is another way of writing that?
<mrvn>
RET is a macro that jumps to R26 and puts the return address into R31 (the zero register)
<mrvn>
emu: The difference between CPS and ret on x86 is that you don#t have a stack in CPS.
<emu>
none of this changes the fact that some level of cooperation is needed, or else you need to jump in and pre-empt it
<mrvn>
emu: of cause you have to jump in if someone misbehaves.
<mrvn>
But the jumping in part is real easy to do.
<mrvn>
Youcan do it with normal ocaml code without asm like setjmp/longjmp needs.
<mrvn>
task.thread1 <- !cont; cont := task.thread2 that can be enough for preemptive mutitasking.
<pattern_>
damn, it's going to take me forever to become fluent with ocaml
<pattern_>
even those little code snippets you gave me are taking some serious effort to understand and see how they all relate to one another
<mrvn>
cps is pretty complex at first
<pattern_>
i did hack a little program together the other day, from bits and pieces of other code and heavy use of ocaml's libraries
<pattern_>
i could just continue to hack away like that, in a mostly imperative style, but i know i wouldn't be using a fraction of ocaml's power
<pattern_>
so do c++ or java have continuations?
<mellum>
There's setjmp and longjmp in C++
<pattern_>
well, that's just a goto, right?
<mellum>
Java doesn't have anything like it, I think
<mellum>
pattern_: it's similar to a continuation
<pattern_>
so it's not like a goto? or are goto's also like continuations?
<mellum>
A goto doesn't save the current context. It just jumps somewhere. You can't return.
<pattern_>
right.. not with a goto alone, but the return address could be saved somewhere
<mellum>
then it's not a goto anymore :)
<pattern_>
yeah
<pattern_>
i guess all of this could be implemented in a plain 'ole imperative style, but then you'd have written a functional language :)
<pattern_>
is using a setjmp and longjmp as easy and elegant in c++ as using continuations are in ocaml?
<mrvn>
pattern_: with CPS you can safe the continuation and call it multiple times. That would be like forking.
<mrvn>
With imperative features a simple "a=17;" would have sideeffects to the next call of the continuation
<pattern_>
mrvn, stop! i can't assimilate any more powerful features of continuations! :D
<lament>
pattern_: setjmp and longjmp don't provide the same functionality.
<lament>
basically, they provide a fairly pathetic and mostly useless subsed of the functionality.
<pattern_>
mrvn, a=17 would not have sideeffects if it was declared in local scope
<mrvn>
pattern_: no, but if its in the scope of the continuation
<mrvn>
Of cause you could use only functional style even in c++.
<pattern_>
yeah
<pattern_>
i wonder if anyone really does
<pattern_>
so continuations are a feature of functional languages in general, not just ocaml?
<lament>
um.
<lament>
No.
<mrvn>
Its a way of doing things thats most easy done in functional languages
<lament>
any language with functions can have continuations.
<lament>
Most don't.
<pattern_>
why don't they?
<mrvn>
All funtional languages have continuations since they are just functions.
<lament>
It's rather hard to implement, it's inefficient, it's just plain weird
<lament>
It causes problems
<pattern_>
seems very useful, though
<lament>
Indeed.
<mrvn>
lament: Your talking about callcc stuff?
<pattern_>
what other problems does it cause, apart from inefficiency?
smklsmkl has joined #ocaml
<pattern_>
(and weirdness) :)
smkl has quit [leguin.freenode.net irc.freenode.net]
liyang_ has quit [leguin.freenode.net irc.freenode.net]
palomer has quit [leguin.freenode.net irc.freenode.net]
skylan has quit [leguin.freenode.net irc.freenode.net]
<lament>
mrvn: yes
smkl has joined #ocaml
liyang_ has joined #ocaml
palomer has joined #ocaml
skylan has joined #ocaml
<mrvn>
lament: we were talking about user level continuations.
<pattern_>
also, isn't the inefficiency of a continuation outweighed by, say, it's application in mrvn's example, where he made the factorial function tail recursive using continuations?
<mrvn>
manual continuations
<lament>
mrvn: if it can be compared to setjmp/longjmp, it looks pretty much like callcc to me
<mrvn>
pattern_: generating a closure is usually more expensive than allocating stack space
<mrvn>
lament: it can't quite
liyang_ has quit [Remote closed the connection]
liyang has joined #ocaml
<pattern_>
ok... so what other uses can continuations be put to, apart from delaying execution?
<mrvn>
pattern_: continuations don't delay the evaluation. Thats what fun and function does.
<pattern_>
oh?
<mellum>
Hm, we used them in our toy parser/compiler, but I can't remember why :)
<pattern_>
i was thinking maybe i could use them in a gp, to pass a bunch of functions as arguments
<mrvn>
Because then all functions are tail recursive and we didn't need a stack, no gotos. Just function calls.
<mrvn>
tail-recursive function calls.
<pattern_>
well, continuations are just function calls with functions as arguments, no? the delayed execution is part of that, right?
<mrvn>
yes
<mrvn>
sort of
<pattern_>
so what am i missing?
MasterID has joined #ocaml
<MasterID>
yop
MasterID has quit [" [FFWorld Script v1.1 - par Mr Jul] disponible sur http://www.ffworld.com"]
smkl has quit [Connection timed out]
clog has joined #ocaml
pattern_ has quit ["..."]
pattern_ has joined #ocaml
pattern_ has quit ["brb"]
pattern_ has joined #ocaml
TachYon26 has joined #ocaml
TachYon26 has quit ["bez ki³y nie ma zaliczenia (z prawd studentek AM)"]
mellum has quit [Read error: 60 (Operation timed out)]
pattern_ has quit ["brb"]
pattern_ has joined #ocaml
mellum has joined #ocaml
ham[let] has joined #ocaml
<ham[let]>
hiho
docelic|away is now known as docelic
Kinners has left #ocaml []
TachYon26 has joined #ocaml
docelic is now known as docelic|away
TachYon26 has quit [Read error: 60 (Operation timed out)]
TachYon26 has joined #ocaml
TachYon26 has quit ["bez ki³y nie ma zaliczenia (z prawd studentek AM)"]
esabb has joined #ocaml
mattam has quit [Read error: 110 (Connection timed out)]
mattam has joined #ocaml
smklsmkl is now known as smkl
lam has quit [Read error: 54 (Connection reset by peer)]
lam has joined #ocaml
ham[let] is now known as han[nwn]
Rhaaw has quit ["leaving"]
Rhaaw has joined #ocaml
<mrvn>
I have two lists of tuples int*int and I want to merge the too without duplicate entries. Any ideas how to do it fast?
<whee>
sort both lists and merge?
<mrvn>
the best I can think of.
<mellum>
Put each entry into a hash table?
<whee>
that'd be expensive
<whee>
you could remove duplicates with a combination of fold and map
<whee>
maybe just fold, hrmf
<mrvn>
mellum: I would have to initialise the hash table or let it grow. Or use a set, which would be as fast as sorting.
<whee>
lemme find the function I'm talking about :\
<whee>
and I don't think ocaml has it in the standard library, easy enough to code though
<mrvn>
I have a matrix, an attribute ('a -> bool) and neighbours (int*int-> int*int list). How do I best get starting with a position all connected fields with the attribute set?
<mellum>
parse error
<mrvn>
Something that doesn't give "Fatal error: exception Stack_overflow" prefered
<mrvn>
I want to do a flood-fill
<mellum>
Ah. Well, do it line-wise, like the Atari :)
<mrvn>
that would be how?
<mrvn>
Fatal error: exception Out_of_memory
<mrvn>
Thats a new one.
<mrvn>
Shouldn't ocaml swap itself to death before something like that happens?
<emu>
why would ocaml swap
<mrvn>
If it runs out of memory it must be using quite a lot.
<mrvn>
And I don't see or hear it using that much ram.
<emu>
it may have a set dynamic space limit
<emu>
you might be able to fiddle with that
<mrvn>
I've seen it using >800 MB and then its swapping.
<mrvn>
So unless it allocates something like 600 MB in one go it shouldn't run out of memory.
<emu>
you can run out of swap space too, you know
<emu>
however
<mrvn>
not within a short time. To much swap to fill up in seconds.
<emu>
hahaha
<emu>
=)
<emu>
I'm sure it could be done
<mrvn>
no, the drives take too long:)
<emu>
slow hd you have there
<emu>
admittedly I'm not an expert
<emu>
but I think there's more to it than simply adding physical ram amt to swap amt
<mrvn>
20-50 MB/s with 1GB swap takes some time.
<mrvn>
I have two BIG records and want to know if they are the same. If I use = it will compare all data, right? DO I need to use (not (a != b))?
<steele>
!= is not ==
<mrvn>
steele: you mean != is not <>
<steele>
!= is equal to (not ==), that's what i wanted to say
<emu>
same record, or have same contents?
<mrvn>
Ah, ok. Lets try.
<whee>
and <> is not =
<whee>
hheh
<mrvn>
whee: beter say (not =), i didn't get that you ment the keyword.
<whee>
haha
<mrvn>
List.filter (fun x -> (y = x) list => Out of memory
<mrvn>
List.filter (fun x -> (y == x) list => works
<mellum>
hmm, = should be a superset of ==
<mrvn>
Just because x is a record with 2 1000000 elements long lists.
<emu>
is == the identity operator?
<steele>
does it what you want? == is pointer equality
<whee>
== is simple pointer checking
<mrvn>
emu: compares the physical address
<emu>
that's why =)
<whee>
= will go and recurse down things
<emu>
identity vs structural equality
<mrvn>
whee: But comparison of a list should use tail-recursion.
<emu>
is it running out of stack or out of heap?
<mrvn>
heap
<emu>
then again
<emu>
ocaml may allocate stacks on the heap..
<emu>
la-de-da
<mrvn>
emu: nope.
<mrvn>
Different exception
<emu>
so that's even weirder
<emu>
why would you run out of heap? hrm
<mrvn>
With = I do, with == I don't.
<emu>
well yeah
<emu>
obviously it's something = is doing
<emu>
what kind of list is it?
<mrvn>
Hmm, I think I know why. *patsch*
<mrvn>
type game = {
<mrvn>
(* doubly linked list of all games *)
<mrvn>
mutable prev : game;
<mrvn>
mutable next : game;
<mrvn>
(* actual game data *)
<emu>
= is trying to operate on the elements of the list too, I presume?
<mrvn>
mutable moves_x : move list;
<mrvn>
mutable moves_o : move list;
<mrvn>
mutable moves : int;
<mrvn>
mutable job : (unit -> unit) option;
<mrvn>
}
<mrvn>
It will recurse into prev, and next forever since they are cyclical.
<emu>
I think you should write your own equality predicate =)
<emu>
the dangers of equality...
<mrvn>
shouldn't = be (== || actual =)?
<emu>
well
<emu>
if two objects are ==
<emu>
that means they are the same object
<mrvn>
emu: how so? let === = or something overloading =?
<emu>
and hence must be =
foxen5 has joined #ocaml
<emu>
eh?
<emu>
List.filter (fun x -> my_equal_predicate y x) list
<emu>
or whatever curried variant
<mrvn>
let === = fun x y -> my_equal_predicate x y
<emu>
you know
<emu>
you don't have to use equal signs =)
<emu>
nothing magical about them
<mrvn>
just everyone will know I do a compare for equalness with ===
<whee>
I suggest the function "thisfunctionismycomparisonfunctionwhichcomparesthingsandissortofnifty"
<emu>
what's === ?
<mrvn>
I like operatros.
<mellum>
then call it ==@+!&*!!
<whee>
mine is self documenting.
<emu>
I prefer names that are readable
<mrvn>
emu: =_waht_ever_you_want_to_call_it
<emu>
like, game=
<mellum>
I prefer peperoni pizza.
<mrvn>
emu: =.... ist an infix operator.
<mrvn>
user defined
<emu>
=game=
<emu>
heh
<mrvn>
that would work.
<whee>
heh
<mellum>
mrvn: but you can't append letters
<emu>
i could care less about the fix
<mrvn>
mellum: yeah, too bad.
<emu>
people get all sorts of fetishes over operators
<mrvn>
Anyway, == is what I need anyway.
<emu>
um
<emu>
if you think so
<emu>
i dunno what you want to do
<mellum>
Hm, I've never needed ==
esabb has quit ["Client Exiting"]
<mrvn>
emu: I have game with a 2D board. I then devide that board into smaller boards (called games). To know what field belongs to what game I have one big arrays of games and I want to see if the current fild belongs to a certain game.
<mrvn>
if games.(i).(j) == current_game
<emu>
that means
<emu>
that games.(i).(j) is bound to precisely the same game that current_game is