00:00:19 -!- heatsink has joined.
02:58:18 -!- deltab has quit ("BitchX-1.0c19 -- just do it.").
03:20:53 -!- deltab has joined.
03:31:24 -!- jDoctor has joined.
03:31:27 -!- slava has joined.
03:32:28 <jDoctor> but if everyone came here -- you know -- to keep the secret, would it still be a secret?
03:33:34 <heatsink> No. Everyone would have to leave here to keep the secret.
03:33:53 <jDoctor> so uh whats the norm discussion here?
03:34:22 <heatsink> This channel isn't active most of the time
03:34:33 <slava> lets make it active!
03:34:38 <heatsink> A while ago, someone wrote a C -> brainfuck compiler
03:34:54 <heatsink> And before that, I wrote an unlambda -> scheme compiler
03:35:17 <heatsink> The conversation about implementing such things can get interesting
03:35:33 <slava> i'm working on stack effect inference for postfix languages
03:36:21 <slava> eg, the stack effect of 2 2 + is [ 0 | 1 ] because it takes no values from the stack, but leaves one
03:36:38 <slava> the stack effect of dup * is [ 1 | 1 ], because it takes one value, duplicates it, multiplies the two duplicates, to yield one value
03:37:02 <slava> it gets more complicated when you have conditionals and recursion, but i have the theory worked out, as well as an algorithm
03:37:07 <heatsink> Doesn't 2 2 + take two values from the stack and then add one?
03:37:20 <slava> + by itself has effect [ 2 | 1 ]
03:37:30 <slava> but 2 2 + has effect [ 0 | 1 ] since the input parameters to + are provided already
03:37:48 <heatsink> so what is the stack effect of printf?
03:37:56 <deltab> 2 has effect [ 0 | 1 ]
03:38:17 <slava> heatsink, no, variadic functions are not handled
03:38:41 <slava> there is an algebra
03:38:57 <slava> [ a | b ] * [ c | d ] = [ a + max(0,c-b) | d + max(0,b-c) ]
03:39:17 <slava> so the stack effect of 2 2 + is [ 0 | 1 ] * [ 0 | 1 ] * [ 2 | 1 ]
03:39:28 <slava> and you can calculate this using the above formula as [ 0 | 1 ]
03:40:27 <jDoctor> it should lead to computer-generated stack effects, right?
03:40:44 <heatsink> You could type-check postfix languages, and express them in prefix or infix form
03:41:16 <slava> i'm working on type inference next.
03:41:29 <heatsink> do both branches of an if-then-else have to have the same stack effect to be legal?
03:41:54 <jDoctor> you cant inference an ifte, can you..
03:41:54 <slava> they don't have to be equal, but balanced. the balance of [ a | b ] is b-a
03:42:34 <slava> so [ dup * ] [ ] ifte is valid
03:42:44 <slava> since after the ifte, the stack height is constant, sonce the two branches are balanced
03:42:56 <slava> effect of dup * is [ 1 | 1 ], effect of [ ] is [ 0 | 0 ]
03:43:11 <slava> so the effect of [ dup * ] [ ] ifte is the maximum element of the two
03:43:16 <slava> which is [ 1 | 1 ] in this case
03:43:54 <slava> this is valid, since i have proofs that balanced sets of stack effects behave just like the maximimal element under pairwise composition
03:44:10 <heatsink> Do you have problems with algorithms that use a sentinel value to terminate recursion?
03:44:26 <slava> words that take variable numbers of arguments off the stack?
03:44:40 <heatsink> yes, and then put the same number of arguments back on
03:44:47 <slava> i don't support these.
03:46:47 <heatsink> What language syntax do you use? Is it taken from an existing language?
03:47:51 <heatsink> Hey, the inventor of factor is named slava too! what a coincidence!
03:48:44 <slava> heatsink, the algorithm and algebra is applicable to any postfix language though
03:48:50 <jDoctor> is that the secret? that these is no secret?
03:49:49 <heatsink> I'm trying to learn type inference. Can you recommend any references?
03:51:06 <heatsink> ooh, you do continuations too!
03:51:40 <slava> yes, but I don't infer stack effects of code involving them.
04:03:24 -!- slava has left (?).
05:29:28 -!- jDoctor has quit ("leaving").
07:59:59 -!- clog has quit (ended).
08:00:00 -!- clog has joined.
08:28:34 <fizzie> why do you have those discussions at 05-06am?
08:44:29 <fizzie> 05:50:44 < heatsink> ooh, you do continuations too!
09:30:01 <heatsink> 11:50:44 < heatsink> ooh, you do continuations too!
09:30:03 <heatsink> 12:50:44 < heatsink> ooh, you do continuations too!
09:30:07 <heatsink> 01:50:44 < heatsink> ooh, you do continuations too!
09:30:23 <heatsink> Well, I'm sure it was 5:50 _somewhere_.
10:13:29 -!- heatsink has quit ("Leaving").
16:09:47 -!- lindi- has quit (Read error: 104 (Connection reset by peer)).
16:13:36 -!- lindi- has joined.
16:28:35 -!- lindi- has quit (tolkien.freenode.net irc.freenode.net).
16:28:35 -!- deltab has quit (tolkien.freenode.net irc.freenode.net).
16:28:35 -!- ZeroOne has quit (tolkien.freenode.net irc.freenode.net).
16:30:48 -!- ZeroOne has joined.
16:34:24 -!- lindi- has joined.
16:34:24 -!- deltab has joined.
16:39:20 -!- lindi-_ has joined.
16:44:31 -!- lindi- has quit (Read error: 110 (Connection timed out)).
16:56:54 -!- lindi-_ has changed nick to lindi-.
18:07:19 -!- andreou has joined.
18:10:45 -!- andreou has quit (Client Quit).
21:46:14 -!- calamari_ has joined.
21:52:10 -!- calamari_ has quit ("Leaving").
22:22:04 <lindi-> anybody thought about building a smart compiler that could optimize by replacing poor algorithms with better ones?
22:22:44 <lindi-> so if the programmer has used e.g. bubble sort the compiler would detect that and actually use quick sort
22:26:19 <fizzie> well: algorithm detection is non-trivial, and it's pretty hard to make sure there are no unexpected effects. "normal" optimizations are hard enough. haven't heard of any compiler that'd do something like that.
22:28:13 <fizzie> methinks it's at least much simpler to provide general algorithms as libraries, and have the programmer use those. why would anyone use bubble sort when the c standard library has a relatively working qsort?
22:29:31 <fizzie> of course implementing something like that might be an interesting exercise, I don't deny that.
22:30:17 <lindi-> indeed, i think i should start by defining some really simple language and experiment with it
22:31:18 <lindi-> ok, but if you ever hear anything like this please let me know :)
22:31:20 <fizzie> not related, but mooz could perhaps say something here about his "random programs" experiments.
22:32:14 <fizzie> apparently he keeps finding composite-number-factoring algorithms at a surprisingly high rate. :p
22:32:16 <lindi-> i thought that if you could express e.g. quick sort in 6 bytes then it would be possible to simply brute force all possible algorithms that fit in 6 bytes
22:34:12 <lindi-> it should prove that the new algorithm 1) does the same as the original algorithm and 2) is faster in all/some/average case/s
22:35:37 <fizzie> me will probably try to sleep some now, have that mat-1.403 exam tomorrow. infinite-dimensional vector spaces, path integrals of complex functions using residues, QR factorizations of matrices. yay!
22:35:52 <lindi-> and i have mat-1.411 :P
22:36:25 <lindi-> discrete math this time
22:36:34 <fizzie> seems like it's the standard 'second mid-term of maths courses' day tomorrow.
22:37:11 <fizzie> besides, I have to demo my scheme-exercise (11 months past the original due date) tomorrow. :p
22:37:13 <lindi-> yep. and indeed, it's probably wise to sleep now
22:37:33 <fizzie> hey, where did my ircnet connection go.
22:37:46 <lindi-> anybody else on the channel: feel free to comment
22:48:30 -!- ZeroOne has quit (Connection timed out).