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:31:30 woos 03:31:37 this place EXISTs 03:31:47 ssh, don't tell anyone! 03:31:56 wont. 03:32:28 but if everyone came here -- you know -- to keep the secret, would it still be a secret? 03:33:34 No. Everyone would have to leave here to keep the secret. 03:33:53 so uh whats the norm discussion here? 03:34:06 nothin' 03:34:22 This channel isn't active most of the time 03:34:33 lets make it active! 03:34:38 A while ago, someone wrote a C -> brainfuck compiler 03:34:41 wow 03:34:54 And before that, I wrote an unlambda -> scheme compiler 03:35:17 The conversation about implementing such things can get interesting 03:35:33 i'm working on stack effect inference for postfix languages 03:35:48 * heatsink has no idea what that is 03:36:05 what is that? 03:36:21 eg, the stack effect of 2 2 + is [ 0 | 1 ] because it takes no values from the stack, but leaves one 03:36:38 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 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 Doesn't 2 2 + take two values from the stack and then add one? 03:37:20 + by itself has effect [ 2 | 1 ] 03:37:29 oh I see 03:37:30 but 2 2 + has effect [ 0 | 1 ] since the input parameters to + are provided already 03:37:48 so what is the stack effect of printf? 03:37:56 2 has effect [ 0 | 1 ] 03:38:09 printf is 0 | 1 03:38:13 I mean 03:38:16 1 | 0 03:38:17 heatsink, no, variadic functions are not handled 03:38:22 ok 03:38:41 there is an algebra 03:38:57 [ a | b ] * [ c | d ] = [ a + max(0,c-b) | d + max(0,b-c) ] 03:39:16 os that composition? 03:39:17 so the stack effect of 2 2 + is [ 0 | 1 ] * [ 0 | 1 ] * [ 2 | 1 ] 03:39:28 and you can calculate this using the above formula as [ 0 | 1 ] 03:40:12 thats some cool stuff 03:40:18 This looks useful 03:40:27 it should lead to computer-generated stack effects, right? 03:40:44 You could type-check postfix languages, and express them in prefix or infix form 03:41:16 i'm working on type inference next. 03:41:29 do both branches of an if-then-else have to have the same stack effect to be legal? 03:41:54 you cant inference an ifte, can you.. 03:41:54 they don't have to be equal, but balanced. the balance of [ a | b ] is b-a 03:42:33 oic 03:42:34 so [ dup * ] [ ] ifte is valid 03:42:44 since after the ifte, the stack height is constant, sonce the two branches are balanced 03:42:56 effect of dup * is [ 1 | 1 ], effect of [ ] is [ 0 | 0 ] 03:42:58 and 0-0 = 1-1 03:43:11 so the effect of [ dup * ] [ ] ifte is the maximum element of the two 03:43:16 which is [ 1 | 1 ] in this case 03:43:39 ok 03:43:54 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 Do you have problems with algorithms that use a sentinel value to terminate recursion? 03:44:26 words that take variable numbers of arguments off the stack? 03:44:40 yes, and then put the same number of arguments back on 03:44:47 i don't support these. 03:45:17 ok 03:46:47 What language syntax do you use? Is it taken from an existing language? 03:47:02 factor 03:47:51 Hey, the inventor of factor is named slava too! what a coincidence! 03:47:57 ;) 03:47:57 hehe.. 03:48:06 sssh... secret 03:48:26 ooh... sorry. 03:48:33 no secret 03:48:44 heatsink, the algorithm and algebra is applicable to any postfix language though 03:48:50 is that the secret? that these is no secret? 03:49:02 s/these/there 03:49:49 I'm trying to learn type inference. Can you recommend any references? 03:51:06 ooh, you do continuations too! 03:51:40 yes, but I don't infer stack effects of code involving them. 03:51:51 oh. 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 why do you have those discussions at 05-06am? 08:39:28 I don't 08:44:29 05:50:44 < heatsink> ooh, you do continuations too! 08:44:32 see, with proof. 09:30:01 11:50:44 < heatsink> ooh, you do continuations too! 09:30:03 12:50:44 < heatsink> ooh, you do continuations too! 09:30:07 01:50:44 < heatsink> ooh, you do continuations too! 09:30:12 :p 09:30:23 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:08:01 hm 18:08:06 heads up 18:10:45 -!- andreou has quit (Client Quit). 21:46:14 -!- calamari_ has joined. 21:52:10 -!- calamari_ has quit ("Leaving"). 22:22:04 anybody thought about building a smart compiler that could optimize by replacing poor algorithms with better ones? 22:22:44 so if the programmer has used e.g. bubble sort the compiler would detect that and actually use quick sort 22:26:19 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 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:28:58 no idea 22:29:31 of course implementing something like that might be an interesting exercise, I don't deny that. 22:30:17 indeed, i think i should start by defining some really simple language and experiment with it 22:31:18 ok, but if you ever hear anything like this please let me know :) 22:31:20 not related, but mooz could perhaps say something here about his "random programs" experiments. 22:31:37 hmm 22:31:40 it's esoteric enough. 22:32:14 apparently he keeps finding composite-number-factoring algorithms at a surprisingly high rate. :p 22:32:16 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 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 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 and i have mat-1.411 :P 22:36:01 is that C1? 22:36:04 yeah 22:36:25 discrete math this time 22:36:34 seems like it's the standard 'second mid-term of maths courses' day tomorrow. 22:37:11 besides, I have to demo my scheme-exercise (11 months past the original due date) tomorrow. :p 22:37:13 yep. and indeed, it's probably wise to sleep now 22:37:33 hey, where did my ircnet connection go. 22:37:46 anybody else on the channel: feel free to comment 22:39:19 so, good night 22:40:55 night. 22:48:30 -!- ZeroOne has quit (Connection timed out).