00:05:01 -!- specbot [~specbot@common-lisp.net] has quit [Remote host closed the connection] 00:05:01 -!- lisppaste [~lisppaste@common-lisp.net] has quit [Remote host closed the connection] 00:10:44 jengle [~jengle@64-252-187-48.adsl.snet.net] has joined #scheme 00:11:55 -!- rdd [~rdd@c83-250-48-164.bredband.comhem.se] has quit [Ping timeout: 240 seconds] 00:12:58 lisppaste [~lisppaste@common-lisp.net] has joined #scheme 00:13:28 minion [~minion@common-lisp.net] has joined #scheme 00:13:33 specbot [~specbot@common-lisp.net] has joined #scheme 00:21:23 saccade [~saccade@209-6-54-113.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com] has joined #scheme 00:24:10 banisterfiend [~horse@27.252.240.91] has joined #scheme 00:26:59 _danb_ [~user@124-149-55-13.dyn.iinet.net.au] has joined #scheme 00:28:25 -!- jengle [~jengle@64-252-187-48.adsl.snet.net] has quit [Read error: Connection reset by peer] 00:28:36 -!- banisterfiend [~horse@27.252.240.91] has quit [Ping timeout: 240 seconds] 00:28:55 jengle [~jengle@64-252-187-48.adsl.snet.net] has joined #scheme 00:34:29 -!- Kerrick [~Kerrick@b11wi-1.nat.iastate.edu] has quit [Quit: Kerrick] 00:37:07 -!- jonrafkind [~jon@crystalis.cs.utah.edu] has quit [Ping timeout: 240 seconds] 00:39:59 oadams [~oadams@h203-28-241-42.trinity.unimelb.edu.au] has joined #scheme 00:44:47 mjonsson [~mjonsson@cpe-98-14-173-5.nyc.res.rr.com] has joined #scheme 00:48:41 -!- turbofail [~user@adsl-69-238-246-201.dsl.pltn13.pacbell.net] has quit [Remote host closed the connection] 01:03:29 banisterfiend [~horse@60.234.38.51] has joined #scheme 01:07:55 -!- githogori [~githogori@242.sub-75-208-28.myvzw.com] has quit [Quit: Leaving] 01:08:42 adu [~ajr@pool-74-96-89-94.washdc.fios.verizon.net] has joined #scheme 01:11:34 -!- wbooze` [~user@xdsl-87-79-58-173.netcologne.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 01:11:56 -!- homie` [~user@xdsl-87-79-58-173.netcologne.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 01:13:59 -!- mmc [~michal@cs27124149.pp.htv.fi] has quit [Quit: Leaving.] 01:14:41 -!- pavelludiq [~quassel@87.246.61.65] has quit [Remote host closed the connection] 01:22:01 Riastradh [debian-tor@fsf/member/riastradh] has joined #scheme 01:27:29 -!- vu3rdd [~vu3rdd@122.167.97.165] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 01:30:17 homie [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 01:32:36 xwl_ [~user@nat/nokia/x-crpdlhkkffaimqne] has joined #scheme 01:34:40 Azuvix [~Azuvix@174-27-51-173.bois.qwest.net] has joined #scheme 01:34:53 wbooze [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 01:35:55 -!- bgs100 [~ian@unaffiliated/bgs100] has quit [Quit: nighty night] 01:44:57 eli: ooh, github fork, eh? Fabulous; I'll take a look 01:51:57 jengle: So, any luck with solving SICP 1.11 yet? :-D 01:53:21 _danb_` [~user@124-149-55-13.dyn.iinet.net.au] has joined #scheme 01:53:35 cky: yeah! i worked on variations of the fibonacci sequence and things began to make sense 01:54:38 -!- _danb_ [~user@124-149-55-13.dyn.iinet.net.au] has quit [Ping timeout: 264 seconds] 01:56:31 jengle: Very good. :-) 01:56:40 Did you ever figure out why I wrote the fractions I did? :-P 02:00:39 (Referring to the -1/3, 5/9, and 2/27.) 02:02:18 cky: no, i'm still in the dark about that. 02:03:46 Okay. I'll explain it to you, if you like. 02:04:08 yeah! 02:04:18 So, when calculating the next value, you need F(n-1), F(n-2), and F(n-3). In my code, those are represented as a, b, and c. 02:04:40 That means if you want to calculate F(1), you need F(0), F(-1), and F(-2). 02:04:52 You know that F(1) = 1, F(2) = 2, and F(3) = 3. 02:05:11 Therefore, you can use the formula's inverse to work backwards to get F(0), F(-1), and F(-2). 02:06:05 Yes, you can embed 1, 2, and 3 in your code instead, but then if someone requests n < 4, your code has to special-case that. For me, that's too messy, so I chose to have one general system that worked for n >= 0. 02:07:00 So, to calculate F(0), use this: F(3) = F(2) + 2*F(1) + 3*F(0) (which is the formula you were given, but substituting 3 for n). 02:07:15 Substituting your starting values, you get: 3 = 2 + 2*1 + 3*F(0). 02:07:36 Move the constant terms to the left, and you get -1 = 3*F(0), and thus F(0) = -1/3. 02:07:47 Apply the same steps to get F(-1) and F(-2). 02:13:01 laurus [~laurus@c-68-40-207-109.hsd1.mi.comcast.net] has joined #scheme 02:26:08 cky: i think i understand. 02:27:32 jengle pasted "f-iter" at http://paste.lisp.org/display/116159 02:29:46 -!- laurus [~laurus@c-68-40-207-109.hsd1.mi.comcast.net] has left #scheme 02:30:41 -!- xwl_ [~user@nat/nokia/x-crpdlhkkffaimqne] has quit [Remote host closed the connection] 02:31:38 -!- Azuvix [~Azuvix@174-27-51-173.bois.qwest.net] has quit [Remote host closed the connection] 02:34:53 jengle: Close, but not quite right. 02:35:01 F(0) != 0, so saying "2 1 0" is wrong. 02:35:13 If you had "2 1 -1/3", then you'd be fine. 02:35:24 (You should run your program and compare the results against the recursive version.) 02:36:07 cky: i did 02:36:30 Try passing in 10. 02:36:47 same output. 02:37:04 1657? 02:38:48 rudybot: eval (define (recur n) (if (<= n 3) n (+ (recur (- n 1)) (* 2 (recur (- n 2))) (* 3 (recur (- n 3)))))) 02:38:51 cky: your sandbox is ready 02:38:55 rudybot: eval (recur 10) 02:38:55 cky: ; Value: 1657 02:39:08 jengle: ^^--- your version needs to result in the same value when 10 is passed in. 02:39:51 jengle: With the version you linked to, you get F(3) = 4 rather than F(3) = 3. 02:43:38 Hi guys :) 02:43:54 cky: i'm getting the same answer.. 02:43:55 franki^: Heya! 02:44:17 jengle annotated #116159 "f-rec and f-iter" at http://paste.lisp.org/display/116159#1 02:44:43 jengle: That's because your f-rec has an off-by-one bug in it. 02:45:02 jengle: Try passing in 3. 02:45:09 If you get back 4 as the answer, your function is buggy. 02:45:17 I'm here to ask for some assistance again; I have this problem trying to enumerate the leaves of a tree, maybe I'm missing something really obvious, but I can't think of a way to "communicate" the number of nodes through the recursion. 02:45:22 cripes... i guess it is. 02:45:44 I have a terrible method using set! here that might make my problem clearer: http://paste.lisp.org/display/116160 02:46:30 franki^: Hehehehe. 02:47:13 I really don't want to use set! or anything similar, but I can't see any other way of doing it... 02:51:20 -!- masm [~masm@2.80.144.108] has quit [Quit: Leaving.] 02:53:42 First, at least have the decency not to use a global variable. Use a different counter for each invocation of NUMBER-LEAVES. 02:56:53 Hehe, okay, let me do that. :) 02:57:42 -!- alexsuraci [~alexsurac@pool-71-188-133-67.aubnin.fios.verizon.net] has quit [Ping timeout: 240 seconds] 02:59:40 githogori [~githogori@adsl-66-123-22-146.dsl.snfc21.pacbell.net] has joined #scheme 03:03:01 elderK [~k@pdpc/supporter/active/elderk] has joined #scheme 03:03:14 alexsuraci [~alexsurac@pool-71-188-133-67.aubnin.fios.verizon.net] has joined #scheme 03:03:54 Next, perhaps consider passing the counter as an argument (say, a pair, whose car is the current count, and into whose car the procedure stores the subsequent count). And then consider: what information is going into this procedure, and what information is coming out? Can you effect the same flow of information, without mutation? 03:07:29 -!- pumpkin [~pumpkin@user-142hbak.cable.mindspring.com] has quit [Remote host closed the connection] 03:09:33 Hey peoples! 03:11:49 pumpkin [~pumpkin@user-142hbak.cable.mindspring.com] has joined #scheme 03:22:49 -!- banisterfiend [~horse@60.234.38.51] has quit [Ping timeout: 252 seconds] 03:25:29 jonrafkind [~jon@jonr5.dsl.xmission.com] has joined #scheme 03:27:30 Well, I feel like I'm sort of going around in circles trying to use a pair or list to pass the information around. But is this getting any closer? http://paste.lisp.org/display/116160#1 03:28:01 From what you said, I'm not sure why using a pair would be any different from using a single variable. 03:29:21 Don't modify quoted literals -- it doesn't work. 03:29:30 > (set-car! '(0) 1) 03:29:30 Error: vm-exception (set-car! '(0) 1) 03:30:23 Instead, write a second procedure. Forget the pairs for a moment; store the count in a local variable with SET!, and use a local recursive procedure that refers to the variable. 03:32:45 banisterfiend [~horse@198-48-0-217-dhcp.cafenet.co.nz] has joined #scheme 03:33:19 Riastradh: Any chance you have a copy of "Representing Control - A study of the CPS Transformation" by Danvy and Filinksi handy? 03:33:31 I have a few questions about it - something I think I misunderstand about the CPS conversion. 03:33:58 Something in their transform doesn't make sense, unless you don't /always/ have to send some result to a continuation. 03:34:22 Sorry, I am extremely busy right now -- I have just decided that it is time to brew a pot of tea. 03:35:00 Interruption of this operation has disastrous consequences, even if pclsring is available. 03:35:08 it's okay. 03:35:16 :) enjoy your tea. 03:50:09 OK, all done brewing tea. 03:52:47 timj__ [~timj@e176197140.adsl.alicedsl.de] has joined #scheme 03:54:06 Welcome back. 03:55:04 My question involves a fair amount of lambda expressions - so, I wonder if I Should take a screenshot of the document I'm referring to, point you to said document or, just write the expressions here. 03:55:58 -!- timj_ [~timj@e176195068.adsl.alicedsl.de] has quit [Ping timeout: 245 seconds] 03:56:41 laurus [~laurus@c-68-40-207-109.hsd1.mi.comcast.net] has joined #scheme 04:00:11 Either way. I have the document handy. 04:00:26 Ah, in that case then - I'll simply point you to the page :) 04:00:29 Page 3, 04:00:38 Classical CPS Transformation 04:00:43 Note that the expression of shift and reset in terms of `CPS' is not valid CPS. 04:00:58 Where they transform \f.\x.\y.(f y) x 04:01:10 :) I've not heard of shift/reset yet. 04:01:35 A bone I have to pick, is in their post-reduction version of the CPS transformation. 04:02:07 If we use the letter Q to denote the translated expression, 04:02:26 then I understand that to use Q, first you must pass it a continuation. ie, (Q k) 04:02:38 which hands the continuation k, the function \f...... 04:02:46 the part that bugs me, 04:03:09 is that you'd call the lambda handed to the continuation, to provide F. 04:03:22 doing that, would immediately return a new lambda, to get a new continuation. 04:04:05 which makes sense, ie : (Q (\n.n f (.... some cont ....))) 04:04:37 except in the context of pure CPS, it confuses me - since the function 'returned' by \f.(bla bla bla), is returned "inline", 04:04:41 it's not handed to a continuation. 04:05:05 Yes, well, that's because their language has only unary functions. 04:05:05 which is why you /can/ call it like ((\f.stuff) f ) 04:05:27 You're supposed to pretend that \f.\k. e is binary, and you're supposed to use it only with two arguments together. 04:05:36 aye, that's what I figured. 04:05:42 If you like, you can rewrite it in your head as \(f, k). e, or as (lambda (f k) e). 04:05:43 I just find it inconsistent. 04:06:03 since, they are going out of their way to provide it in "pure lambda calculus" terms, like, 04:06:14 and then breaking that... 04:06:30 which brings me to the need to clarify my understanding of what CPS' 04:06:32 purpose is. 04:06:56 Simply to rearrange the program, to be more regular, so that the compiler can more easily reason about and optimize, right? 04:07:04 -!- laurus [~laurus@c-68-40-207-109.hsd1.mi.comcast.net] has left #scheme 04:07:25 It's like, when I'm translating scheme-style lambda stuff to CPS, I can handle it quite fine. 04:07:45 But reading the many papers on CPS and various optimizations, the different notations, evaluation strategies... it messes it all up. 04:08:16 To clarify, I guess my question is simply: 04:08:27 in the \f.\k. 04:08:47 the user of that is expected to call it as (( ) ) 04:09:01 ie, the curried way of handling multiple parameters, right? 04:09:12 Yes. 04:09:22 which means in this case, and only in this case, an "immediate" return is acceptable? 04:09:34 Yes. 04:09:47 ie: if we consider the \k. to be the intermediate result, in this case, it does not need to be explicitly named. 04:10:23 :) So, with that out of the way, 04:10:41 I was also wondering if you had any tips or general advice that you could impart, that could maybe make this a little easier going. 04:10:45 like, the understanding of these papers. 04:10:53 Since, I'm trying very hard to dig as deep as I can, to gain the insights for myself. 04:11:03 But I find even Plotkin's paper to be quite difficult to digest. 04:11:21 Apart from that - I'm starting to think that simply finding a copy of Alonzo's original paper from the 30s to be the only real solution. 04:11:54 Alternatively - if I understand CPS well enough to translate things by hand, do I really need to dive this deep, to create a translator similar to your own? 04:12:18 Since, the special transformations you made during... translation, piqued my interest :) 04:12:21 Remember that most of what they're doing is just using clumsy notation for Scheme... 04:12:35 And writing math when they're trying to write interpreters or compilers. 04:12:36 (So, I've been scouting for information - like on lambda lifting, studying the various reductions, alpha, beta, eta) 04:12:46 Yeah, that's what I figured too. 04:12:56 It's like they are using the mathematical notation purely for the hell of it, sometimes. 04:13:01 at least, it seems that way in a lot of papers. 04:13:36 Like, take \f.\x.\y.(f y) x 04:13:53 to me, that's (lambda (f x y) ((f y) x)) 04:14:01 and in cPS, I'd have that as: 04:16:15 (lambda (k f x y) (f (lambda (fy) (fy (lambda (fyx) (k fyx)) x)) y)) 04:16:56 that is, we evaluate (f y), pass the result to (lambda (fy) ...), evaluate (fy x), pass that to (lambda (fyx) ...), then pass the end result ((f y) x) to the continuation. 04:17:27 assuming (f y) returns something we can apply. 04:17:32 right? 04:17:55 Also assuming that all functions take a continuation as their first argument. 04:18:23 (and hey, I'm sorry if I'm spamming you - I'm just really eager to understand this stuff, you know?) 04:20:08 Except for the tail reduction you could have made, that looks right. 04:20:25 (Usually I find it clearer to put the continuation last, because it is usually a 04:20:41 ...much larger expression than the operand, and the ^M key is too close to the `m' key.) 04:21:01 vu3rdd [~vu3rdd@nat/cisco/x-mmssrpbrsaepecve] has joined #scheme 04:21:26 aye. 04:21:36 Would you mind elucidating hte tail reduction? 04:22:15 Eta-reduction of continuations, basically. 04:22:29 Why write (lambda (fyx) (k fyx)) when you can write k? 04:22:49 good point 04:22:55 I could just have (fy k x) 04:23:08 In a naive interpreter, in fact, writing (lambda (fyx) (k fyx)) instead of k will destroy proper tail recursion. 04:23:29 aye - you'd assume that would be reduced or handled in a sane way. 04:24:11 :) which now brings me to ask more about the optimizations you do, in your translator. 04:24:21 Reading the logs, you mentioned something called a meta-continuation. 04:24:27 :) I'm not sure I quite understand what you meant by that. 04:24:30 Riastradh pasted "super-simplified CPS conversion procedure" at http://paste.lisp.org/display/116163 04:25:21 (Beware -- that code was written on the spur of the moment and only lightly tested.) 04:25:47 (np, it'll take me some time to study and understand it :)) 04:26:07 (I assume match simply checks to see if term, is a term or something?) 04:26:50 Yes. , if I recall correctly, implements it in standard, portable Scheme. 04:27:14 :) cool. 04:27:21 Um...maybe not `yes'. I don't understand what you just said, now that I read it again. 04:27:23 :P I'm looking forward to trying to answer the reader question. 04:27:37 It's okay - either way, I'll read the match.scm and hopefully understand what it's for. 04:28:03 MATCH is an inverse to QUASIQUOTE. 04:28:08 (and a lot more) 04:28:37 (let ((x 5)) (match `(foo ,x) (`(foo ,y) y))) yields 5, for instance. 04:29:06 Don't worry about MATCH -- you can read it instead as (cond ((lambda? term) (let ((parameter (lambda-parameter term)) (body (lambda-body term))) ...]. 04:29:37 sweet. 04:29:54 (Compare to page 4 of Danvy & Filinski's paper, giving the specification of the transformation.) 04:30:59 where they have numbered the lambda terms and applications? 04:31:23 Yes. 04:31:39 btw, what exactly do they mean by "residual cps terms" ? 04:31:48 do they mean the intermediate transformations of the larger expression? 04:32:05 -!- MichaelRaskin [~MichaelRa@195.91.224.225] has quit [Remote host closed the connection] 04:32:12 ie, if x is in some expression, then \k.(k x) would the residual cps term? 04:32:23 I think they mean administrative redexes (redices?) -- reducible terms that were introduced by the CPS transformation. 04:32:32 Or perhaps they mean the output of the CPS transformation. 04:32:39 It's kind of ambiguous. 04:33:03 :) Thank you for the help, Riastradh. 04:33:12 It's going to be fun understanding the basic translator and match :D 04:33:25 Anyway, if I recall correctly from a dim recollection of the paper (I read it only a long time ago), everything important that they say is also said by the Scheme code I just pasted. 04:33:26 It'll be a good exercise for testing my knowledge of syntax-rules too :D 04:33:57 Um... I don't think you actually want to read the MATCH implementation. 04:34:05 That scary, huh? :) 04:34:19 pavelludiq [~quassel@87.246.61.65] has joined #scheme 04:34:22 No, it's just tedious and not very insightful. 04:34:40 *elderK* nods 04:34:43 Out of curiosity, 04:34:52 and please, don't take this as generic flattery :) 04:35:04 but, you're one of the most knowledgable scheme folks here. 04:35:09 I was just wondering how you came to acquire all of that knowledge. 04:35:18 Did you seek out papers in a thirst for knowledge, too? 04:35:44 I dunno... 04:35:45 It may have been more of a hunger. 04:35:50 Like the munchies. 04:35:53 Heh. :P 04:36:09 Was just wondering if you were formally taught these things or if you did it in the style of hacker tradition :) 04:38:14 I wasn't taught anything formally about PL theory. 04:38:39 In any case, I just tend to flood myself with information about programming language theory and such, and hope that by reading enough of the related papers, and rereading them many times, too, that eventually, things will click. 04:39:17 :) Any books that you found useful? 04:39:22 I recommend that you translate the papers you read into programs -- especially the ones that are hard to understand, full of dingbats. 04:39:34 Some people have recommended some texts on denotational semantics. 04:39:37 And aye, that's good advice. 04:39:58 Often it turns out that what the authors were trying to say is actually just that this or that program computes this or that useful thing and doesn't fail in this or that obvious way. 04:39:58 (I found using coloring pencils to help navigate their parens handy too - that or entering their craziness into emacs) 04:40:28 (And often that's how they started, before translating their program from Scheme or ML or Haskell into dingbats.) 04:40:43 -!- mjonsson [~mjonsson@cpe-98-14-173-5.nyc.res.rr.com] has quit [Remote host closed the connection] 04:41:17 ~_~ It seems pointless, turning it into dingbat form. It doesn't make it easier to understand, and isn't that really the point of papers? To spread new information and ideas? 04:41:32 Or is it really just about getting grants and making things obscure to seem more hardcore? 04:41:38 :( I'd sure hope it isn't the case. 04:44:36 There is one technical merit to writing dingbats instead of Scheme programs. 04:44:44 If typeset well enough, dingbats tend to fit in displays in two-column A4 paper better than Scheme programs. 04:45:22 Aye, and I guess it also helps keep the idea language-independent? 04:45:53 *Riastradh* shrugs. 04:46:40 :P maybe they sit back and question about how they can make the paper more exciting. 04:46:46 and they come up with "fun symbols!" 04:46:47 :P 04:48:39 :) Well, I'm off to study the source. 04:48:51 Thanks again, Riastradh, for taking the time to help. :) 04:48:54 Anyway, there's a lot of confusion about CPS in the literature, and I don't really know why; it was probably only exacerbated by a theorem envy that encourages authors to say so little with so many theorems that they miss the forest for the trees. 04:49:08 Amen! 04:49:48 CPS itself, seems really straightforward - name temporary values - so that there are no "intermediate" calls. 04:50:06 so that function invocation doesn't have parameters, that are themselves function invocations. 04:50:22 If you read about flow analysis and CPS or ANF, you'll probably encounter a serious wave of confusion about this that really puzzles me. If you encounter this, I'd be happy to try to condense the issue. 04:51:03 I'm finding papers or books on flow analysis to be pretty hard to find, actually. 04:51:09 at least related to CPS or lisp in general. 04:52:09 There are dozens at . I don't have a good suggestion for a starting point, though; an obvious choice is Olin Shivers' dissertation, but frankly I don't think it's particularly easy to understand. 04:52:53 Well, even a hard-to-understand paper can at least provide direction via it's bibliography, I guess. 04:53:07 :) I hope to get the Rabbit paper printed this week. 04:53:25 Well...from the bibliography of Olin's dissertation, you'll find only papers that are harder to understand. 04:53:33 :P Great. 04:53:43 I didn't find the Rabbit paper to be especially enlightening, but I rather liked Kranz's dissertation on Orbit. 04:54:36 If you want to read about writing a native-code compiler for a strict functional-oriented programming language, I recommend Kranz's dissertation. 04:54:38 Same here. 04:54:57 The Orbit paper was really well done, I feel. 04:55:18 They also referenced stuff within their own paper, well, too. 04:55:33 Like, if you didn't get some term they were using or, forgot, you could jump back to where it was defiend pretty easily. 04:55:41 Lot sof papers leave you to search like a maniac... 04:56:02 :) Downed all shiver's papers on data/control flower. 04:56:04 er, flow 05:00:58 -!- _danb_` is now known as ______danb______ 05:02:14 -!- ______danb______ is now known as _danb_ 05:02:48 Maybe Matt Might has written a good introduction to flow analysis of Scheme by abstract interpretation. 05:03:37 MichaelRaskin [~MichaelRa@195.178.216.22] has joined #scheme 05:08:00 http://matt.might.net/#papers ? 05:08:01 :) 05:09:13 -!- _danb_ [~user@124-149-55-13.dyn.iinet.net.au] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 05:10:07 Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has joined #scheme 05:10:23 Hello everyone. 05:11:25 ? 05:11:34 Yo, Neuroneutron! 05:11:35 ! 05:11:43 Hey :P 05:11:57 Glad there are people out there. :P 05:12:11 cky: I don't see where I have an off-by-one error in my recursive function.. 05:12:42 I just started on Scheme yesterday. Is it easy to master? 05:13:11 Neuroneutron: How long is a piece of string? 05:13:22 well put, jengle. 05:13:24 I don't know. Just started. 05:13:33 I'd say it' san easy language to pick up, but one that is hard to master, like many other languages. 05:13:39 I see. 05:13:45 Nothing is easy to master, except tic-tac-toe, and global thermonuclear war. 05:13:46 I find that Lisp is really nice to program in. 05:13:50 the main thing I learned about scheme is that more o ften than not, many of hte things taht seem incredibly difficult, are actually dead obvious. 05:14:00 so obvious, that that is the reason they are so hard, if that makes any sense whatsoever. 05:14:07 it's definitely a language whwere you get what you give. 05:14:10 But I heard that Scheme is "minimal" 05:14:13 What does that mean? 05:14:37 Why include what the user can easily construct themselves? 05:14:43 It doesn't mean much. 05:14:59 Ok. 05:15:05 -!- banisterfiend [~horse@198-48-0-217-dhcp.cafenet.co.nz] has quit [Ping timeout: 255 seconds] 05:15:19 Is the book "Structure and Interpretation of Programs" a good place to start learning Scheme? 05:15:48 Not exactly. But it's a good place to start learning various things, and it uses Scheme. 05:16:10 Are there any other good articles to pick up Scheme? 05:19:54 ? 05:20:53 aidalgol [~user@132.181.15.184] has joined #scheme 05:21:06 Are there any good articles to pick up Scheme? 05:21:26 And also, is Scheme good for AI programming? I'm just experimenting with stuff. 05:28:03 ? 05:28:07 -!- Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has quit [Quit: Leaving] 05:32:38 -!- aidalgol [~user@132.181.15.184] has quit [Ping timeout: 255 seconds] 05:33:07 Neuronman [~Neuroneut@bb219-75-97-253.singnet.com.sg] has joined #scheme 05:33:28 -!- Neuronman [~Neuroneut@bb219-75-97-253.singnet.com.sg] has left #scheme 05:34:14 Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has joined #scheme 05:36:45 Hello again. 05:39:09 the description of "order of growth" in sicp is confusing to me... k_1*f(n) <= R(n) <= k_2*f(n) 05:39:30 banisterfiend [~horse@198-48-0-119-dhcp.cafenet.co.nz] has joined #scheme 05:39:36 where "we say that R(n) has order of growth O(f(n))" 05:39:52 can someone please explain? 05:40:47 Surely you're reading Theta(f(n)), not O(f(n)) there. 05:41:35 Riastradh: yes. 05:43:04 -!- metasyntax [~taylor@72.86.89.174] has quit [Ping timeout: 252 seconds] 05:43:32 The full definition of R(n) is in Theta(f(n)) [or, a little more formally, R is in Theta(f)] is that there exist some positive real numbers N, k_1, and k_2, such that for any n > N, k_1 f(n) <= R(n) <= k_2 f(n). The picture is that if you draw the graph of R, then you can draw a scaled-down graph of f (grow the graph of f by k_1) and a scaled-up graph of f (shrink it by k_2), and at some point off to the right (N), the graph of R lies completely 05:44:10 -!- banisterfiend [~horse@198-48-0-119-dhcp.cafenet.co.nz] has quit [Ping timeout: 252 seconds] 05:45:29 Example: Draw the graph of R(n) = 2 n^2 + 3 n + 4. Then, on top of it, draw the graph of f(n) = 3 n^2, and also draw the graph of f(n) = (1/2) n^2. 05:46:30 In all three cases, you'll get parabolas, squished in different ways. 05:48:06 rdd [~rdd@c83-250-48-164.bredband.comhem.se] has joined #scheme 05:50:42 aidalgol [~user@118.148.151.231] has joined #scheme 05:51:03 Riastradh: Wouldn't you be "scaling down" the graph of f by "shrinking it by k_2"? 05:51:23 -!- Riastradh [debian-tor@fsf/member/riastradh] has quit [Ping timeout: 245 seconds] 05:54:19 Riastradh [debian-tor@fsf/member/riastradh] has joined #scheme 05:54:40 Can anyone recommend a good book on mastering Scheme? 05:55:07 jengle, sorry, yes, I mixed up which one was smaller and which one was larger. I was also truncated: ...and at some point off to the right (past N on the x-axis), the graph of R lies completely between the two scaled graphs of f. 05:55:58 metasyntax [~taylor@72.86.89.174] has joined #scheme 05:58:19 Riastradh: how did you come to choose those particular equations? 05:58:24 (Specifically, I wrote the message without the parentheses about growing and shrinking f, and then edited it to insert them, and inserted them the wrong way around.) 05:58:47 I made them up, arbitrarily. 06:00:40 -!- aidalgol [~user@118.148.151.231] has quit [Ping timeout: 252 seconds] 06:01:43 aidalgol [~user@118.148.152.234] has joined #scheme 06:02:43 Once you've drawn those graphs, try to find a line that the graph of the function R(n) = 2 n^2 + 3 n + 4 lies completely below, or a cubic that R lies completely above (for positive inputs -- the left side of the graph is irrelevant here, because the inputs usually represent the sizes of data structures or problems, which are never negative). 06:04:10 -!- pavelludiq [~quassel@87.246.61.65] has quit [Remote host closed the connection] 06:04:28 (If you don't have a plotting program handy, that's OK -- the functions I gave you are easy enough to graph using pencil and paper and a little hand arithmetic.) 06:07:28 -!- elderK [~k@pdpc/supporter/active/elderk] has quit [Quit: Leaving...] 06:08:41 Riastradh: I don't understand what the math is implying. 06:09:01 I understand the symbols but the meaning is lost on me. 06:09:15 It's a language for describing how algorithms scale up to large inputs. 06:09:44 Let's say n is the size of your problem, and R(n) is the number of steps needed to compute a solution to your problem. 06:10:39 Okay, so far that makes sense. 06:10:57 You might find that the program taking R(n) steps to compute a solution to your problem runs fast enough for the small inputs you tested, but when you want to run it on the entire Google index, you might want to know whether it's worth your time to wait for an answer. 06:11:55 One way to do this is to find some function f(n) whose graph, at some point off to the right, lies *completely* above that of R(n). Thus, for sufficiently large inputs, your program certainly won't take more than f(n) steps. 06:12:29 Now, f is usually some function that is very simple: f(n) = n, or f(n) = n^2, or f(n) = 2^n. 06:13:23 Let's say R(n) fits under k f(n) for some k, far enough off to the right. 06:14:13 Let's suppose you notice your program is a little slower than you're happy with when n = 100. So you tweak your program so that it runs twice as fast when n = 100. 06:14:45 Better yet, you tweak it so that it runs four times as fast when n = 100 -- that is, it takes a quarter the time it originally took. 06:15:24 Now you want to throw your program at an input where n = 200. (You've just gone from processing a hundred web pages to processing two hundred ones.) 06:16:08 -!- Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has quit [Quit: Leaving] 06:17:07 What do you think you can say about how much time the original program and the tweaked program will run on the input where n = 200? 06:17:41 _danb_ [~user@124-149-55-13.dyn.iinet.net.au] has joined #scheme 06:18:16 Oops... I meant: `Let's say R(n) fits under k n^2 for some k, far enough off to the right.' 06:19:04 (If you're totally lost, just say so.) 06:19:20 nego [~nego@c-76-16-30-244.hsd1.il.comcast.net] has joined #scheme 06:20:02 Riastradh: what is f(n) computing? 06:20:32 It's usually just a familiar function that gives you a rough idea of the shape of another function, when you zoom way out. 06:21:35 -!- aidalgol [~user@118.148.152.234] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 06:21:36 And when you say "above", you don't mean that the minima of the function is above the minima of R(n), right? 06:23:01 (minimum? vertex?) 06:23:02 When I say that `the graph of f(n) lies above the graph of R(n) far enough to the right', I mean that if you draw the graphs, and look at inputs far enough to the right (along the positive x-axis), eventually your pencil will always be higher up on the page when you're drawing f(n) than when you're drawing R(n), no matter how much farther to the right you go. 06:23:31 Ah, I see. 06:24:11 Example: Graph the parabola y = x^2, and the line y = x + 3. Although near zero the graph of y = x + 3 lies above y = x^2, if you look to the right a little ways, eventually the parabola crosses the line, and stays above it for the rest of the paper, however large your piece of paper is. 06:27:00 Riastradh: Alright, I understand that now. 06:27:54 I imagine if the program is processing 200 websites, it would take twice the amount of time? 06:28:05 (or steps) 06:28:41 Well...maybe. Let me switch the situation around a little bit. Suppose the graph of R(n) lies *above* the graph of f(n) = k n^2 far enough out to the right (where 100 and 200 are both far enough out to the right). 06:29:04 Say f(n) = n^2, for simplicity; forget k. 06:29:57 If R(100) = 20000, can R(200) = 40000, if R(n) lies above n^2 (far enough to the right)? 06:32:05 yes...? 06:32:16 I am absolutely guessing. I'm sorry! 06:32:29 I need to get this. 06:32:36 Well, let's see. R(100) = 20000 > 100^2. So that's OK. But is 40000 > 200^2? 06:33:31 no. 06:33:44 So clearly R(200) cannot be 40000. 06:33:56 What's the *smallest* value R(200) can have? 06:34:11 40000 06:34:16 er.. 06:34:18 -!- jonrafkind [~jon@jonr5.dsl.xmission.com] has quit [Ping timeout: 245 seconds] 06:34:36 20000? 06:34:59 Remember that R(n) has to lie above n^2. 06:35:06 (Well, it can coincide with n^2, too.) 06:36:54 Oops. I should check my arithmetic. 06:37:10 I'm confused because I don't have an equation for R(n) 06:37:19 Sorry, 40000 is correct. I meant to use 30000 there, not 40000. 06:37:32 All you know about R(n) is that it's at least n^2, for sufficiently large values of n. 06:37:47 So it might be n^2 + 1, or it might be 1023 n^2, or something like that. 06:40:28 Sorry about the bad choice of numbers conjured out of the air. Anyway, the point is that if your program takes at least n^2 steps to solve a problem of size n, if you double the input size, you will at least *quadruple* the number of steps it takes to solve the problem. 06:41:40 And this is true even if it takes only (1/2) n^2 steps to solve a problem of size n, or (1/10000) n^2 steps. 06:43:52 Similarly, suppose you have a program that takes a day to run on a hundred web pages, and the graph of the program's running time as a function of the number of web pages looks like a parabola. A day is too long for you to wait, so you tweak your program to speed it up, and now it takes only a quarter of a day to run. But the graph still looks like a parabola. How many web pages can you process in a day now? 06:44:27 (A program's `running time' is the number of steps it takes to compute, sorry.) 06:46:56 You can process 4 times as many web pages 06:48:42 Well...unfortunately, no; actually, you can process only twice as many web pages. Since the graph of running time vs input size looks like a parabola, if you double the input size, the amount of time it takes quadruples. 06:51:18 This is because if f(n) = n^2, then f(2 n) = (2 n)^2 = 4 n^2 = 4 f(n). 07:00:45 mmc [~michal@cs27124149.pp.htv.fi] has joined #scheme 07:07:13 -!- ski [~slj@c-8911e055.1149-1-64736c10.cust.bredbandsbolaget.se] has quit [Read error: Connection reset by peer] 07:12:38 jbd` [~user@fw1-aus1.rackspace.net] has joined #scheme 07:16:19 -!- jbd [~user@fw1-aus1.rackspace.net] has quit [Ping timeout: 250 seconds] 07:17:14 -!- jbd` [~user@fw1-aus1.rackspace.net] has quit [Ping timeout: 272 seconds] 07:17:25 seangrove [~user@c-71-198-44-87.hsd1.ca.comcast.net] has joined #scheme 07:17:39 gravicappa [~gravicapp@ppp85-141-166-249.pppoe.mtu-net.ru] has joined #scheme 07:21:53 -!- Riastradh [debian-tor@fsf/member/riastradh] has quit [Remote host closed the connection] 07:23:21 Riastradh [debian-tor@fsf/member/riastradh] has joined #scheme 07:27:46 Riastradh: I need to go, I'm incredibly tired and it's 3:27a, 07:27:50 *am 07:27:56 but I will ask you about this late 07:27:58 *later 07:28:00 thanks again 07:28:00 jbd` [~user@fw1-aus1.rackspace.net] has joined #scheme 07:28:09 -!- jengle [~jengle@64-252-187-48.adsl.snet.net] has quit [Quit: jengle] 07:35:03 -!- vu3rdd [~vu3rdd@nat/cisco/x-mmssrpbrsaepecve] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 07:37:36 vu3rdd [~vu3rdd@nat/cisco/x-dgntcwdgjmtnucok] has joined #scheme 07:45:24 elderK [~k@pdpc/supporter/active/elderk] has joined #scheme 08:46:54 Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has joined #scheme 08:47:53 Can someone provide an answer to this question in "Structure and Interpretation of Programs": A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process. 09:01:41 -!- githogori [~githogori@adsl-66-123-22-146.dsl.snfc21.pacbell.net] has quit [Ping timeout: 265 seconds] 09:03:36 iterative: I would take the (initial) vector (0 1 2) and scalar multiply with (1 2 3); that is apply the function to get the next value f(3). Then make the vector (by shifting) (1 2 f(3)), and iterate this process, until you get the f(n) 09:05:34 How about the "recursive" way? 09:08:05 -!- REPLeffect [~REPLeffec@69.54.115.254] has quit [Read error: Connection reset by peer] 09:14:59 I don't understand the question: do you want a naive (tree) recursion; a function which just invokes 3 times itself (unless n < 3)? Or do you need a tail-recursive function? 09:15:49 The question asked for a tree-recursion function. 09:21:01 then the body of the function is: 09:21:01 (if (< n 3) 09:21:01 n 09:21:01 (+ (f (- n 1)) 09:21:01 (f (- n 2) 09:21:01 (- n 3))) 09:21:02 Thanks! I spent almost an hour on it! Recursion is really quite confusing at times. 09:21:02 also, this iterative process, can be made faster: instead of (1 2 3) one might matrix multiply w/ suitable matrix (1 2 3) the first row, to obtain (f(n+1) f(n+2) f(n+3)). 09:21:02 -!- `micro [~micro@www.bway.net] has quit [Ping timeout: 255 seconds] 09:21:03 homie` [~user@87.79.58.173] has joined #scheme 09:21:13 I'm still quite confused at the tree recursive example. Can you explain it in depth? 09:22:32 well, you see the code. by induction, you can prove, that in fact it computes the desired function, and that it finishes. 09:23:14 yes, I assumed the function is in fact called f: so I should have written: 09:23:14 (define (f n) 09:23:14 (if ....)) 09:23:44 So basically what you did was to call the function on the function on the function .. etc.? 09:24:07 REPLeffect [~REPLeffec@69.54.115.254] has joined #scheme 09:24:23 -!- homie [~user@xdsl-87-79-58-173.netcologne.de] has quit [Ping timeout: 255 seconds] 09:24:23 yes, I invoke the function with another (lesser) argument. 09:24:48 But what do you mean by "lesser"? 09:25:59 pavelludiq [~quassel@87.246.61.65] has joined #scheme 09:26:01 to compute f(N) I invoke f(N-1), f(N-2) ... 09:26:18 I see. 09:26:32 oh, the body in fact should have been (+ (f (- n 1)) (* 2 (f (- n 2) ....) 09:26:38 So it's reducing the argument by calling the function? 09:27:10 Thanks :) 09:28:45 It's hard to switch to a recursive mode of thought, because we don't usually think of things that way. 09:33:53 -!- kephas [~pierre@AStrasbourg-551-1-63-120.w83-194.abo.wanadoo.fr] has quit [Ping timeout: 276 seconds] 09:36:27 kephas [~pierre@AStrasbourg-551-1-42-36.w92-148.abo.wanadoo.fr] has joined #scheme 09:38:31 -!- jbd` [~user@fw1-aus1.rackspace.net] has quit [Read error: Connection reset by peer] 09:38:49 jbd` [~user@fw1-aus1.rackspace.net] has joined #scheme 09:49:07 -!- adu [~ajr@pool-74-96-89-94.washdc.fios.verizon.net] has quit [Quit: adu] 09:52:14 sid3k [~user@li140-93.members.linode.com] has joined #scheme 09:56:00 -!- Neuroneutron [~Neuroneut@bb219-75-97-253.singnet.com.sg] has left #scheme 10:05:29 -!- pavelludiq [~quassel@87.246.61.65] has quit [Read error: Connection reset by peer] 10:10:08 -!- Quadrescence [~Quad@unaffiliated/quadrescence] has quit [Ping timeout: 245 seconds] 10:14:45 -!- kilimanjaro [~kilimanja@unaffiliated/kilimanjaro] has quit [Quit: Leaving] 10:18:03 -!- homie` [~user@87.79.58.173] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 10:18:24 -!- wbooze [~user@xdsl-87-79-58-173.netcologne.de] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 10:33:44 schmir [~schmir@mail.brainbot.com] has joined #scheme 10:35:01 homie [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 10:35:58 -!- qebab [~robb@jaguar.stud.ntnu.no] has quit [Ping timeout: 245 seconds] 10:36:26 -!- homie [~user@xdsl-87-79-58-173.netcologne.de] has quit [Read error: Connection reset by peer] 10:37:11 qebab [~robb@jaguar.stud.ntnu.no] has joined #scheme 10:40:25 homie [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 10:41:14 -!- homie [~user@xdsl-87-79-58-173.netcologne.de] has quit [Read error: Connection reset by peer] 10:42:20 masm [~masm@bl19-144-108.dsl.telepac.pt] has joined #scheme 10:44:55 mbohun [~mbohun@ppp115-156.static.internode.on.net] has joined #scheme 10:47:31 pavelludiq [~quassel@87.246.31.34] has joined #scheme 10:52:14 homie [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 10:54:57 -!- homie [~user@xdsl-87-79-58-173.netcologne.de] has quit [Client Quit] 10:59:23 homie [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 11:03:09 wbooze [~user@xdsl-87-79-58-173.netcologne.de] has joined #scheme 11:08:06 -!- vu3rdd [~vu3rdd@nat/cisco/x-dgntcwdgjmtnucok] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 11:10:56 wbooze` [~user@xdsl-78-34-104-46.netcologne.de] has joined #scheme 11:12:20 homie` [~user@xdsl-78-34-104-46.netcologne.de] has joined #scheme 11:12:46 -!- homie` [~user@xdsl-78-34-104-46.netcologne.de] has quit [Read error: Connection reset by peer] 11:12:54 -!- wbooze` [~user@xdsl-78-34-104-46.netcologne.de] has quit [Client Quit] 11:13:04 -!- wbooze [~user@xdsl-87-79-58-173.netcologne.de] has quit [Ping timeout: 252 seconds] 11:13:17 -!- homie [~user@xdsl-87-79-58-173.netcologne.de] has quit [Ping timeout: 255 seconds] 11:16:52 homie [~user@xdsl-78-34-104-46.netcologne.de] has joined #scheme 11:18:45 wbooze [~user@xdsl-78-34-104-46.netcologne.de] has joined #scheme 11:59:20 pnkfelix [~Adium@c-71-225-45-140.hsd1.nj.comcast.net] has joined #scheme 11:59:27 -!- pnkfelix [~Adium@c-71-225-45-140.hsd1.nj.comcast.net] has quit [Client Quit] 11:59:50 pnkfelix [~Adium@c-71-225-45-140.hsd1.nj.comcast.net] has joined #scheme 12:16:11 -!- Axsuul [~someone@97-93-99-133.static.mtpk.ca.charter.com] has quit [Ping timeout: 250 seconds] 12:27:36 -!- mbohun [~mbohun@ppp115-156.static.internode.on.net] has quit [Quit: Leaving] 12:28:57 mmc1 [~michal@cs27120227.pp.htv.fi] has joined #scheme 12:31:43 -!- mmc [~michal@cs27124149.pp.htv.fi] has quit [Ping timeout: 240 seconds] 12:47:27 aisa [~aisa@c-68-35-167-179.hsd1.nm.comcast.net] has joined #scheme 12:52:43 -!- mmc1 [~michal@cs27120227.pp.htv.fi] has quit [Ping timeout: 240 seconds] 12:59:06 HG` [~HG@xdsl-92-252-114-166.dip.osnanet.de] has joined #scheme 12:59:19 -!- pavelludiq [~quassel@87.246.31.34] has quit [Remote host closed the connection] 13:05:30 mmc [~michal@cs27124149.pp.htv.fi] has joined #scheme 13:15:04 rpg [~rpg@216.243.156.16.real-time.com] has joined #scheme 13:25:24 jbd [~user@fw1-aus1.rackspace.net] has joined #scheme 13:36:10 vu3rdd [~vu3rdd@122.166.147.250] has joined #scheme 13:40:31 -!- jbd [~user@fw1-aus1.rackspace.net] has quit [Remote host closed the connection] 13:40:48 jbd [~user@fw1-aus1.rackspace.net] has joined #scheme 13:41:18 Chat7627 [ayvzdq@69.41.179.202] has joined #scheme 13:41:54 hello every1 13:42:40 -!- Chat7627 is now known as PinkLips 13:43:50 -!- PinkLips [ayvzdq@69.41.179.202] has quit [Client Quit] 13:46:06 fradgers- [~fradgers-@5e04acf0.bb.sky.com] has joined #scheme 13:48:54 -!- elderK [~k@pdpc/supporter/active/elderk] has quit [Quit: Leaving...] 13:53:55 EbiDK [~ebi@3e6b7ac3.rev.stofanet.dk] has joined #scheme 13:58:35 *cky* apologises to a rather currently-absent jengle: the off-by-one is at my end. 13:59:13 I misread the question as: f(n) = n for n <= 3, as opposed to n < 3. That completely invalidates all the solutions I've posted, of course. 13:59:51 Sorry about the confusion I caused! 14:02:25 -!- jbd` [~user@fw1-aus1.rackspace.net] has quit [Remote host closed the connection] 14:02:25 -!- jbd [~user@fw1-aus1.rackspace.net] has quit [Remote host closed the connection] 14:04:23 pavelludiq [~quassel@87.246.31.34] has joined #scheme 14:12:07 cky pasted "SICP 1.11 iterative solution (fixed)" at http://paste.lisp.org/display/116170 14:12:19 -!- _danb_ [~user@124-149-55-13.dyn.iinet.net.au] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 14:13:46 ...hindsight says I could just have pasted a revision to my last solution. 14:17:59 cky annotated #116025 "Fixed version :-)" at http://paste.lisp.org/display/116025#1 14:19:20 -!- pavelludiq [~quassel@87.246.31.34] has quit [Remote host closed the connection] 14:26:13 "Paste in haste, repent at leisure" 14:28:04 ventonegro [~alex@c9346090.virtua.com.br] has joined #scheme 14:32:59 firecrow8 [~fcrow@69.38.169.34] has joined #scheme 14:45:03 jengle [~jengle@64-252-187-48.adsl.snet.net] has joined #scheme 14:46:24 Quadrescence [~Quad@unaffiliated/quadrescence] has joined #scheme 14:48:52 -!- oadams [~oadams@h203-28-241-42.trinity.unimelb.edu.au] has quit [Read error: Connection reset by peer] 14:49:14 bweaver [~user@75-148-111-133-Chattanooga.hfc.comcastbusiness.net] has joined #scheme 15:04:18 -!- gravicappa [~gravicapp@ppp85-141-166-249.pppoe.mtu-net.ru] has quit [Ping timeout: 245 seconds] 15:09:41 pavelludiq [~quassel@87.246.31.34] has joined #scheme 15:19:00 gravicappa [~gravicapp@ppp85-141-167-37.pppoe.mtu-net.ru] has joined #scheme 15:27:15 -!- ventonegro [~alex@c9346090.virtua.com.br] has quit [Quit: ventonegro] 15:29:45 leppie [~lolcow@196-215-20-67.dynamic.isadsl.co.za] has joined #scheme 15:30:53 tupi [~david@186.205.37.15] has joined #scheme 15:36:22 femtoo [~femto@95-89-197-196-dynip.superkabel.de] has joined #scheme 15:43:35 Axius [~darkstar@92.85.214.143] has joined #scheme 15:44:29 dnm [~dnm@c-68-34-57-169.hsd1.va.comcast.net] has joined #scheme 15:55:58 -!- Quadrescence [~Quad@unaffiliated/quadrescence] has quit [Read error: Connection reset by peer] 15:56:45 How do I use cons? 15:57:00 (cons a b) 15:57:11 where a and b are some variables. 15:57:52 (cons i '(2 4 5 6)) like this 15:58:46 How do I define a function? 15:59:15 (define (f x) (add1 x)) 15:59:18 -!- Riastradh [debian-tor@fsf/member/riastradh] has quit [Ping timeout: 245 seconds] 16:00:34 rudybot: eval (define (prepend-an-x seq) (cons 'x seq)) 16:00:40 rudybot: eval (prepend-an-x (list 1 2 3)) 16:00:40 *offby1: ; Value: (x 1 2 3) 16:00:44 gosh, it works 16:00:56 rudybot: eval (prepend-an-x (prepend-an-x (list 1 2 3))) 16:00:56 *offby1: ; Value: (x x 1 2 3) 16:00:59 ooh exciting 16:02:47 -!- mmc [~michal@cs27124149.pp.htv.fi] has quit [Read error: Operation timed out] 16:04:31 mmc [~michal@cs27120227.pp.htv.fi] has joined #scheme 16:06:17 I get an error: (define add (x y) (+ x y)) 16:06:46 when I do that. 16:08:59 define: bad definition: (add (x y) (+ x y)) 16:10:02 (define (add x y) (+ x y)) 16:12:12 yep 16:12:16 notice the parens 16:12:30 Axius: amusingly, there's a dialect of Lisp in which what you did is the correct thing. 16:12:38 it works 16:14:46 rudybot: eval (define add +) 16:14:51 just to confuse you further 16:14:55 rudybot: eval (add 1 2 3 4 99) 16:14:55 *offby1: ; Value: 109 16:15:21 my 'add' is better than yours, because mine takes any number of arguments, whereas yours always demands exactly two. 16:15:22 So there. 16:16:13 too many arguments to: (add 1 2 4 99) 16:17:38 jengle: http://paste.lisp.org/display/116025#1 16:17:55 jengle: My bad with the earlier off-by-one comment; I misread the question. 16:18:10 jengle: I thought f(n) = 3 for n <= 3, as opposed to n < 3. 16:18:24 jengle: So, your solution is fine; what I pasted above is my fixed solution. 16:19:15 cky: thank god! i was so excited to have a solution, you really killed my buzz haha 16:19:29 offby1, What implementation do use you? 16:20:04 jengle: I'm sorry! :-( 16:20:07 yes, common lisp for example would do (defun add (x y) (+ x y)) because it's silly and treats functions differently 16:20:10 jengle: I hope your buzz comes back. :-) 16:20:36 so silly, it's a barrel of laughs 16:21:21 ray: Hahaha. 16:22:04 mao [~h@91.78.208.173] has joined #scheme 16:22:43 -!- mmc [~michal@cs27120227.pp.htv.fi] has quit [Ping timeout: 240 seconds] 16:23:13 jengle: You can still look at my solution if you like. I changed the fractions a bit, but I still use the F(-1) and F(-2) constants, so that we don't calculate two extra values that will never be used. 16:23:20 jengle: But, correctness-wise, your solution is fine. 16:24:20 (And really, at this point, the differences between the versions is really just splitting hairs: the number of computations is exactly the same between your version and mine.) 16:24:45 simon__ [~simon@84-75-166-95.dclient.hispeed.ch] has joined #scheme 16:25:56 -!- Axius [~darkstar@92.85.214.143] has quit [Read error: Connection reset by peer] 16:26:22 -!- simon__ [~simon@84-75-166-95.dclient.hispeed.ch] has quit [Client Quit] 16:34:32 mmc [~michal@cs27124149.pp.htv.fi] has joined #scheme 16:36:20 -!- antoszka [~antoszka@unaffiliated/antoszka] has quit [*.net *.split] 16:36:20 -!- Adrinael [~adrinael@barrel.rolli.org] has quit [*.net *.split] 16:36:20 -!- elly [~elly@atheme/member/elly] has quit [*.net *.split] 16:36:42 elly [~elly@atheme/member/elly] has joined #scheme 16:38:00 antoszka [~antoszka@unaffiliated/antoszka] has joined #scheme 16:38:36 -!- EbiDK [~ebi@3e6b7ac3.rev.stofanet.dk] has quit [Read error: Connection reset by peer] 16:41:28 Adrinael [~adrinael@barrel.rolli.org] has joined #scheme 16:44:19 -!- Jafet [~Jafet@unaffiliated/jafet] has quit [Ping timeout: 240 seconds] 16:52:09 -!- mmc [~michal@cs27124149.pp.htv.fi] has quit [Ping timeout: 240 seconds] 16:55:07 jonrafkind [~jon@crystalis.cs.utah.edu] has joined #scheme 17:01:34 Riastradh [debian-tor@fsf/member/riastradh] has joined #scheme 17:12:44 cky: I'm not sure that I'm capable of discovering that difference myself... but hopefully someday I will be. I'm going through a pre-calc book and SICP to prepare myself for courses in computer science. 17:16:14 mmc [~michal@cs27124149.pp.htv.fi] has joined #scheme 17:30:40 -!- snorble [~none@s83-179-14-105.cust.tele2.se] has left #scheme 17:31:13 teurastaja [~teurastaj@modemcable231.29-131-66.mc.videotron.ca] has joined #scheme 17:33:21 snorble [~snorble@s83-179-14-105.cust.tele2.se] has joined #scheme 17:34:23 jengle: :-) 17:35:01 my math skills are definitely lacking 17:35:35 me two 17:35:40 algorithms also 17:35:42 jengle: Why do you say that? :-) 17:35:48 teurastaja: Yes, my algorithm skills are lacking. 17:36:04 scheme heavily stresses algorithmic creativity 17:36:21 Riastradh was trying to explain order of growth to me and I'm still confused about it. 17:36:28 I want to get it so I can move on in SICP 17:36:38 thats why its important to be able to make "schemes" by yourself 17:36:40 jengle: You don't need to know much maths for that. You just need to look at curves. 17:36:54 kilimanjaro [~kilimanja@ip24-255-34-109.tc.ph.cox.net] has joined #scheme 17:36:54 -!- kilimanjaro [~kilimanja@ip24-255-34-109.tc.ph.cox.net] has quit [Changing host] 17:36:54 kilimanjaro [~kilimanja@unaffiliated/kilimanjaro] has joined #scheme 17:36:55 jengle: So, linear rate of growth looks like a straight line. 17:37:17 jengle: Logarithmic looks like it gets flatter and flatter as it heads out right. 17:37:42 jengle: Exponential looks like it gets sharper and sharper as it heads out right. 17:38:03 jengle: Polynomial ones, well, it depends. :-) 17:38:30 cky: nice observation 17:38:52 Polynomial ones don't get as sharp as exponential ones, nor as flat as logarithmic ones. :-) 17:39:05 Most importantly: Quick-growing = bad, slow-growing = good. :P 17:39:11 franki^: Hehehehehe. 17:39:34 so logarithmic algorithms are good? 17:40:21 jengle: Certainly better than any of the other ones I mentioned. 17:40:35 Constant is even better: its curve is simply a flat line. 17:41:03 kuribas [~user@d54C43271.access.telenet.be] has joined #scheme 17:41:27 what does the curve describe? time and space? 17:41:32 s/and/or/ 17:41:39 and/or is right. :-) 17:41:48 So, there's time-complexity and space-complexity. 17:41:54 It's important to know which one you're talking about. 17:42:04 The curve can describe either case. 17:42:17 Inded, it depends, but previously you were talking about the number of steps, which is taken to be time. 17:42:24 Yep. 17:42:37 Unless you have a crazy machine in which the number of steps doesn't correlate with time! :) 17:43:45 so how would i describe the order of growth of say... a recursive procedure that computes the fibonacci sequence? 17:44:10 i want to understand how to apply those curves to the code 17:47:08 jengle: Keep a counter of how many times you recurse. 17:47:27 jengle: Then, call your function with different values of n, and see how much that changes the counter. 17:48:04 wuj [~wuj@pool-74-108-204-117.nycmny.east.verizon.net] has joined #scheme 17:48:20 -!- wuj [~wuj@pool-74-108-204-117.nycmny.east.verizon.net] has quit [Excess Flood] 17:48:38 wuj [~wuj@pool-74-108-204-117.nycmny.east.verizon.net] has joined #scheme 17:49:08 Yeah, as far as I understand it, you have to be sort of "abstract" with what constitutes a step. Unless you know you're actually talking about CPU instructions. Which I think is almost impossible in Scheme. :) 17:49:42 But, I guess it doesn't need to be an exact science, just to give you an idea of how the running time of the function grows 17:49:58 Indeed. 17:50:11 I'd like to be able to look at a function I write and determine whether or not it's worth waiting for it to compute. 17:50:22 mjonsson [~mjonsson@cpe-98-14-173-5.nyc.res.rr.com] has joined #scheme 17:50:23 ...which is the whole point of big-o notation, right? 17:50:28 jengle: Uh huh. 17:50:41 so how would I describe a function using big-o notation? 17:51:17 I learnt this by trying to solve project Euler problems. After five minutes of waiting for it to return you realise you need to look at the algorithm more closely. ;) 17:52:23 jengle: It deends on the function, but basically you graph size-of-input against time-to-compute 17:52:51 -!- mmc [~michal@cs27124149.pp.htv.fi] has left #scheme 17:53:17 why is it then that SICP describes order-of-growth using obscure inequalities? 17:53:19 Where size-of-input could be the length of a list, the number of variables, the size of an array. Whatever the functions acts upon 17:53:33 franki: some scheme compilers compile to native code 17:54:17 Inequalities are good, because you can "trap" the order of growth of the function between two much simpler functions without ever knowing the real order-of-growth function, that might be very complicated 17:54:24 (If you're lucky) 17:54:51 teurastaja: Yes, but reading Scheme code and knowing what native code that would compile to is well beyond my skills at least. :) 17:56:10 well... considering all the optimizations that must be done with the assembly... 17:56:28 and if were talking about a JIT then thats mostly impossible 17:57:32 with static profiling (i mean stateful, done once), if you read the results, its possible 17:58:17 but with JIT compilers... its live so its hard to keep track of everything at runtime... 18:04:52 femtooo [~femto@95-89-197-196-dynip.superkabel.de] has joined #scheme 18:06:25 cky: did you manage to solve ex. 1-13? 18:06:46 jengle: Lemme look at it. :-) 18:08:02 -!- femtoo [~femto@95-89-197-196-dynip.superkabel.de] has quit [Ping timeout: 276 seconds] 18:09:34 I think I have it, but it seems so trivial that I feel like I'm doing something wrong. 18:11:26 jengle pasted "sicp ex. 1-13" at http://paste.lisp.org/display/116177 18:13:28 -!- teurastaja [~teurastaj@modemcable231.29-131-66.mc.videotron.ca] has quit [Ping timeout: 245 seconds] 18:14:26 Oh, that's interesting. I didn't even think of writing a program for that exercise. I have a long-hand written proof 18:15:13 franki^: Maybe that's what the authors expected 18:15:20 I don't know if I'm capable of doing it :( 18:16:23 If you don't have any experience of inductive proofs it might be a bit difficult to think up on your own. :) 18:17:01 jengle: Indeed, the authors expected a rigorous proof (using induction, as the question stated). :-) 18:17:14 jengle: What you want to show are two things: 18:18:51 1. Fib(n) = (phi^n - psi^n)/sqrt(5) 18:19:06 2a. That psi^1 < 0.5 (so that rounding works) 18:19:20 -!- mjonsson [~mjonsson@cpe-98-14-173-5.nyc.res.rr.com] has quit [Remote host closed the connection] 18:19:22 Oops, that |psi^1| < 0.5, I meant. 18:19:46 2b. That psi^n gets closer to 0 as n gets bigger. 18:20:37 Of course, 2a implies 2b, because for any number x where |x| < 1, x^n does get smaller as n gets bigger. 18:20:59 (where "smaller" means "closer to 0", in this instance). 18:30:07 Okay, I set fib(2) = phi^2 / sqrt(5) and did out the math 18:30:24 actually, i just simplified phi^2 / sqrt(5) 18:30:48 and got: (3sqrt(5) + 5) / 10 18:31:14 i put it in the calculator and it yielded ~ 1, which is the same as fib(2) 18:31:19 is that enough proof? 18:32:00 It depends on your level of maths. :-) 18:32:03 i haven't done any sort of mathematical "proof" since geometry in 9th or 10th grade 18:32:15 Okay, in that case that's enough proof in your case, I guess. 18:32:21 :( 18:32:25 If you've done university maths, then usually something more rigorous is required. 18:37:47 jengle: Did you read Fare's file about Fibonacci sequence? 18:39:46 -!- araujo [~araujo@gentoo/developer/araujo] has quit [Read error: Operation timed out] 18:40:40 cky: not yet, but i have it bookmarked 18:43:16 -!- vu3rdd [~vu3rdd@122.166.147.250] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 18:45:46 araujo [~araujo@gentoo/developer/araujo] has joined #scheme 18:46:25 mmc [~michal@cs27120227.pp.htv.fi] has joined #scheme 18:49:43 -!- leppie [~lolcow@196-215-20-67.dynamic.isadsl.co.za] has quit [Ping timeout: 245 seconds] 18:52:38 leppie [~lolcow@196-215-20-67.dynamic.isadsl.co.za] has joined #scheme 19:01:14 -!- araujo [~araujo@gentoo/developer/araujo] has quit [Ping timeout: 264 seconds] 19:05:05 araujo [~araujo@gentoo/developer/araujo] has joined #scheme 19:06:28 stis [~stis@1-1-1-39a.veo.vs.bostream.se] has joined #scheme 19:08:28 -!- seangrove [~user@c-71-198-44-87.hsd1.ca.comcast.net] has quit [Ping timeout: 245 seconds] 19:19:48 -!- pnkfelix [~Adium@c-71-225-45-140.hsd1.nj.comcast.net] has quit [Read error: Connection reset by peer] 19:20:08 pnkfelix [~Adium@c-71-225-45-140.hsd1.nj.comcast.net] has joined #scheme 19:20:11 -!- MichaelRaskin [~MichaelRa@195.178.216.22] has quit [Read error: Connection reset by peer] 19:20:43 -!- rpg [~rpg@216.243.156.16.real-time.com] has quit [Remote host closed the connection] 19:21:11 rpg [~rpg@216.243.156.16.real-time.com] has joined #scheme 19:21:26 -!- rpg [~rpg@216.243.156.16.real-time.com] has quit [Read error: Connection reset by peer] 19:21:46 rpg [~rpg@216.243.156.16.real-time.com] has joined #scheme 19:33:48 jewel [~jewel@196-215-88-116.dynamic.isadsl.co.za] has joined #scheme 19:35:36 -!- HG` [~HG@xdsl-92-252-114-166.dip.osnanet.de] has quit [Quit: Leaving.] 20:02:16 jengle: :-) 20:02:45 cky: i had a look at fare's link, but i'm not sure what is so significant about it. 20:02:53 a lot of it seems like a summary of what is being taught in sicp 20:03:01 jengle: It explores Fibonacci sequences in depth. :-) 20:08:41 Fare [~Fare@ita4fw1.itasoftware.com] has joined #scheme 20:14:43 Axsuul [~someone@97-93-99-133.static.mtpk.ca.charter.com] has joined #scheme 20:17:01 -!- jewel [~jewel@196-215-88-116.dynamic.isadsl.co.za] has quit [Ping timeout: 252 seconds] 20:29:16 phao [~phao@189.107.128.150] has joined #scheme 20:29:41 is the object oriented model SICP teaches prototype based? 20:33:58 *eli* drums fingers in offby1's general direction 20:43:01 -!- Euthydemus [~euthydemu@vaxjo3.23.cust.blixtvik.net] has quit [Quit: leaving] 20:45:05 Euthydemus [~euthydemu@vaxjo3.23.cust.blixtvik.net] has joined #scheme 20:49:50 -!- phao [~phao@189.107.128.150] has quit [Ping timeout: 240 seconds] 20:54:53 bgs100 [~ian@unaffiliated/bgs100] has joined #scheme 21:00:55 MichaelRaskin [~MichaelRa@195.91.224.225] has joined #scheme 21:11:14 -!- mao [~h@91.78.208.173] has quit [Remote host closed the connection] 21:13:45 phao [~phao@189.107.175.242] has joined #scheme 21:22:48 -!- femtooo [~femto@95-89-197-196-dynip.superkabel.de] has quit [Quit: Leaving] 21:33:02 -!- schmir [~schmir@mail.brainbot.com] has quit [Read error: Connection reset by peer] 21:39:34 -!- stepnem [~stepnem@176.119.broadband10.iol.cz] has quit [Quit: ZNC - http://znc.sourceforge.net] 21:39:44 schmir [~schmir@mail.brainbot.com] has joined #scheme 21:42:24 -!- acarrico [~acarrico@pppoe-68-142-40-104.gmavt.net] has quit [Read error: Connection reset by peer] 21:43:31 stepnem [~stepnem@176.119.broadband10.iol.cz] has joined #scheme 21:53:28 -!- pavelludiq [~quassel@87.246.31.34] has quit [Read error: Connection reset by peer] 21:54:02 -!- schmir [~schmir@mail.brainbot.com] has quit [Remote host closed the connection] 22:05:07 -!- pygospa [~pygospa@217.191.164.147] has quit [Disconnected by services] 22:05:16 TheRealPygo [~pygospa@217.191.169.68] has joined #scheme 22:08:07 -!- stis [~stis@1-1-1-39a.veo.vs.bostream.se] has quit [Remote host closed the connection] 22:17:55 -!- alaricsp [~alaric@relief.warhead.org.uk] has quit [Remote host closed the connection] 22:19:11 -!- phao [~phao@189.107.175.242] has quit [Quit: Leaving] 22:20:35 -!- aisa [~aisa@c-68-35-167-179.hsd1.nm.comcast.net] has quit [Ping timeout: 240 seconds] 22:21:00 alaricsp [~alaric@relief.warhead.org.uk] has joined #scheme 22:28:26 -!- MichaelRaskin [~MichaelRa@195.91.224.225] has quit [Ping timeout: 255 seconds] 22:30:32 cinch [~cinch@unaffiliated/cinch] has joined #scheme 22:30:33 -!- gravicappa [~gravicapp@ppp85-141-167-37.pppoe.mtu-net.ru] has quit [Remote host closed the connection] 22:35:44 -!- jengle [~jengle@64-252-187-48.adsl.snet.net] has quit [Quit: jengle] 22:42:01 aisa [~aisa@c-68-35-167-179.hsd1.nm.comcast.net] has joined #scheme 22:44:58 -!- samth [~samth@punge.ccs.neu.edu] has quit [Quit: Ex-Chat] 22:52:23 saint_cypher [~rjspotter@70-36-245-104.dsl.static.sonic.net] has joined #scheme 23:02:01 -!- saint_cypher [~rjspotter@70-36-245-104.dsl.static.sonic.net] has quit [Ping timeout: 252 seconds] 23:02:22 -!- kuribas [~user@d54C43271.access.telenet.be] has quit [Quit: ERC Version 5.3 (IRC client for Emacs)] 23:05:18 -!- rdd [~rdd@c83-250-48-164.bredband.comhem.se] has quit [Read error: Operation timed out] 23:08:21 -!- bweaver [~user@75-148-111-133-Chattanooga.hfc.comcastbusiness.net] has quit [Ping timeout: 250 seconds] 23:12:42 schmir [~schmir@p54A90E8E.dip0.t-ipconnect.de] has joined #scheme 23:12:50 -!- pchrist [~spirit@gentoo/developer/pchrist] has quit [Ping timeout: 255 seconds] 23:18:57 saint_cypher [~rjspotter@70-36-245-104.dsl.static.sonic.net] has joined #scheme 23:21:41 bombshelter13b [~bombshelt@76-10-149-209.dsl.teksavvy.com] has joined #scheme 23:23:03 Quadrescence [~Quad@unaffiliated/quadrescence] has joined #scheme 23:24:12 jengle [~jengle@64-252-187-48.adsl.snet.net] has joined #scheme 23:25:47 -!- bombshelter13b [~bombshelt@76-10-149-209.dsl.teksavvy.com] has quit [Client Quit] 23:38:36 -!- schmir [~schmir@p54A90E8E.dip0.t-ipconnect.de] has quit [Remote host closed the connection] 23:40:20 -!- saint_cypher [~rjspotter@70-36-245-104.dsl.static.sonic.net] has quit [Quit: Leaving.] 23:40:23 wbooze` [~user@xdsl-78-34-104-226.netcologne.de] has joined #scheme 23:40:42 homie` [~user@xdsl-78-34-104-226.netcologne.de] has joined #scheme 23:42:38 -!- homie [~user@xdsl-78-34-104-46.netcologne.de] has quit [Ping timeout: 245 seconds] 23:43:14 -!- wbooze [~user@xdsl-78-34-104-46.netcologne.de] has quit [Ping timeout: 264 seconds] 23:48:15 Jafet [~Jafet@unaffiliated/jafet] has joined #scheme 23:50:44 -!- fradgers- [~fradgers-@5e04acf0.bb.sky.com] has left #scheme 23:54:23 samth [~samth@punge.ccs.neu.edu] has joined #scheme 23:56:15 -!- mmc [~michal@cs27120227.pp.htv.fi] has quit [Ping timeout: 240 seconds]