2009 Aug 30 23:53:37  -*- inimino got up to 3.62
2009 Aug 30 23:56:46  <aamar> solid
2009 Aug 30 23:56:50  -*- aamar got up to 3.66
2009 Aug 30 23:57:16  <inimino> ah
2009 Aug 31 00:00:52  <inimino> mariorz: you around?
2009 Aug 31 00:04:48  <inimino> perhaps not
2009 Aug 31 00:05:46  <aamar> looks like no
2009 Aug 31 00:06:03  <inimino> alright, should we start?
2009 Aug 31 00:06:07  <aamar> yes, let's
2009 Aug 31 00:06:19  <inimino> ok
2009 Aug 31 00:06:24  <inimino> 3.47
2009 Aug 31 00:06:32  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.47
2009 Aug 31 00:07:01  <aamar> Actually of the time I spent these two weeks, most of it was on 3.47 and 3.60
2009 Aug 31 00:07:05  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L914-953
2009 Aug 31 00:10:03  <inimino> wow
2009 Aug 31 00:10:48  <aamar> I don't think my solution to (a) is a good one.
2009 Aug 31 00:10:53  <inimino> these look similar, I notice in a) we took the mutex in different places
2009 Aug 31 00:11:12  <aamar> I think yours makes much more sense.
2009 Aug 31 00:11:31  <aamar> Basically have one mutex control the semaphore itself, and keep a counter.
2009 Aug 31 00:11:48  <inimino> and you have additional mutexes inside
2009 Aug 31 00:11:57  <aamar> The problem asked for "mutexes" which I thought meant that there was some reasonably good solution involving a list of mutexes.
2009 Aug 31 00:12:13  <inimino> ah
2009 Aug 31 00:12:16  <aamar> Yeah, but they're useless, as far as I can tell.
2009 Aug 31 00:12:40  <aamar> The counter seems far simpler and more effective.
2009 Aug 31 00:14:06  <inimino> looks like yours would work
2009 Aug 31 00:14:12  <aamar> I think it would.
2009 Aug 31 00:14:21  <aamar> For (b) we have pretty similar answers.
2009 Aug 31 00:15:47  <inimino> I'm still reading yours
2009 Aug 31 00:15:52  <aamar> 3.48 ?
2009 Aug 31 00:16:03  <aamar> ok
2009 Aug 31 00:16:09  <inimino> I see we loop in a different place in acquire-one/acquire-first-free
2009 Aug 31 00:16:19  <inimino> though it doesn't look like a significant difference
2009 Aug 31 00:17:27  <inimino> hm, good point about release-one not being atomic
2009 Aug 31 00:17:48  <aamar> yes, you have the loop in dispatch -- equivalent, I think
2009 Aug 31 00:18:01  <inimino> the problem being that two calls to release-one at the same time might both 'free' the same cell
2009 Aug 31 00:18:22  <aamar> right, right
2009 Aug 31 00:18:32  <inimino> so the semaphore becomes gradually filled with dead entries
2009 Aug 31 00:18:44  <aamar> hard to fix that without having some function that does the opposite of "test-and-set!"
2009 Aug 31 00:18:57  <inimino> I guess the way to do that would be to store the number of the cell when you set it
2009 Aug 31 00:18:58  <aamar> or using a mutex -- which seems to go against the spirit of the problem.
2009 Aug 31 00:19:28  <inimino> yes
2009 Aug 31 00:19:53  <aamar> hm -- how does that fix it?
2009 Aug 31 00:20:08  <inimino> well, it doesn't quite fix it
2009 Aug 31 00:20:20  <inimino> or does it
2009 Aug 31 00:20:40  <inimino> I think it does
2009 Aug 31 00:20:52  <inimino> say you have a counter in acquire-first-free
2009 Aug 31 00:21:21  <inimino> you just store the index of the cell on which test-and-set! succeeded
2009 Aug 31 00:21:42  <inimino> then when you release, you release that same cell, regardless of whatever other cells are free or not
2009 Aug 31 00:22:32  <aamar> okay, but then you need to wrap a mutex around access to that cell-index and releasing that cell.
2009 Aug 31 00:22:45  <inimino> so given that no other process can have successfully taken that same cell, the free operation will always have a unique effect
2009 Aug 31 00:23:18  <aamar> serialize { retrieve cell-index, clear that cell, clear that cell-index }
2009 Aug 31 00:23:55  <aamar> It works, but it suggests that the only correct solution that solves for that is to use test-and-set! like a mutex
2009 Aug 31 00:23:57  <inimino> you already have the cell-index stored in a variable inside the semaphore
2009 Aug 31 00:24:16  <aamar> that I know
2009 Aug 31 00:24:30  <inimino> ok, so why do you need to serialize clearing it?
2009 Aug 31 00:24:39  <aamar> I'm looking at the case where two processes attempt to 'release at the same time.
2009 Aug 31 00:24:49  <inimino> nothing else could have gotten that same index until you do clear it
2009 Aug 31 00:24:53  <aamar> You need to block for the case where both grab the same cell-index and release the same cell.
2009 Aug 31 00:25:22  <inimino> so any two that are releasing will be releasing different cells, and I think there's no problem
2009 Aug 31 00:25:50  <aamar> so if the code enters the-semaphore's dispatch, both calling 'release...
2009 Aug 31 00:25:57  <inimino> at most n processes will have taken the semaphore at any time, and at each one will have a unique cell-index stored in its local state
2009 Aug 31 00:26:10  <aamar> oh I see
2009 Aug 31 00:26:16  <inimino> between 0 and n-1
2009 Aug 31 00:26:17  <aamar> but
2009 Aug 31 00:26:31  <aamar> then you're creating local state per-each process
2009 Aug 31 00:26:41  <inimino> so then each one enters 'release, each one clears a different cell
2009 Aug 31 00:26:48  <aamar> each process needs to remember which index it's pointing to -- how do you store that per the process?
2009 Aug 31 00:27:16  <inimino> oh you're right, we didn't have that previously
2009 Aug 31 00:27:47  <aamar> you could pass something like a process id to the 'acquire call, and require it to be passed back when you run 'release.
2009 Aug 31 00:27:54  <inimino> it's have to pass back a token in 'acquire and then provide that token when calling ... yeah
2009 Aug 31 00:28:07  <inimino> something like that
2009 Aug 31 00:28:09  <inimino> ok
2009 Aug 31 00:28:12  <aamar> I think it works.
2009 Aug 31 00:28:39  <aamar> This guy wrote (b) very much like your (a) solution, but essentially replicated mutex-like functionality with test-and-set!
2009 Aug 31 00:28:40  <aamar> http://eli.thegreenplace.net/2007/10/26/sicp-334/
2009 Aug 31 00:29:25  <aamar> (I only look at online help on SICP during/after these meetings, btw :))
2009 Aug 31 00:30:19  <inimino> ah yeah
2009 Aug 31 00:31:03  <inimino> that seems like a more correct solution than mine
2009 Aug 31 00:31:09  <inimino> to (b)
2009 Aug 31 00:31:52  <inimino> he just kind of inlined the test-and-set! mutex implementation into (a)
2009 Aug 31 00:32:27  <aamar> yes
2009 Aug 31 00:32:47  <inimino> alright, I think we've killed this one, next?
2009 Aug 31 00:33:46  <aamar> yes, let's go
2009 Aug 31 00:34:02  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L956-993
2009 Aug 31 00:34:59  <inimino> ok
2009 Aug 31 00:35:06  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.48
2009 Aug 31 00:37:13  <inimino> these look similar
2009 Aug 31 00:37:42  <aamar> ha, yes, very -- I should have factored out the "let" -- then they would be the same, looks like.
2009 Aug 31 00:37:58  <inimino> yeah
2009 Aug 31 00:38:15  <inimino> alright, next one?
2009 Aug 31 00:38:19  <aamar> yes
2009 Aug 31 00:38:20  <aamar> 3.49
2009 Aug 31 00:38:21  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L995-1004
2009 Aug 31 00:38:45  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.49
2009 Aug 31 00:38:59  <aamar> This one was a bit useless, because the hint is basically the answer.
2009 Aug 31 00:39:40  <inimino> yeah, exactly
2009 Aug 31 00:39:50  <inimino> alright, moving on
2009 Aug 31 00:40:09  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.50
2009 Aug 31 00:40:15  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1007-1015
2009 Aug 31 00:40:28  <aamar> exactly the same
2009 Aug 31 00:40:43  <inimino> indeed
2009 Aug 31 00:41:00  <inimino> this streams section was fun
2009 Aug 31 00:41:14  <aamar> Yeah, completely agree.
2009 Aug 31 00:41:17  <inimino> and I was glad to be out of 3.4
2009 Aug 31 00:41:49  <inimino> 3.51?
2009 Aug 31 00:42:01  <aamar> That's what they want!  They want you to hate program state!
2009 Aug 31 00:42:13  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1016-1020
2009 Aug 31 00:42:16  <inimino> hehe, yeah
2009 Aug 31 00:42:52  -*- inimino is a puppet, reaches up and feels strings
2009 Aug 31 00:42:58  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.51
2009 Aug 31 00:43:06  <aamar> ha
2009 Aug 31 00:43:21  <aamar> oh, forgot to include the actual return value of these calls
2009 Aug 31 00:43:48  <inimino> hehe
2009 Aug 31 00:44:13  <inimino> well, 3.52?
2009 Aug 31 00:44:26  <aamar> yes
2009 Aug 31 00:44:26  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1021-1042
2009 Aug 31 00:45:51  <aamar> same, except for the display-stream output
2009 Aug 31 00:46:02  <inimino> whoops, looks like I display-streamed the wrong thing
2009 Aug 31 00:46:06  <inimino> oh well
2009 Aug 31 00:46:34  <inimino> 3.53: http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.53
2009 Aug 31 00:46:42  <inimino> looks like these are the same as well...
2009 Aug 31 00:47:08  <inimino> and 3.54...
2009 Aug 31 00:47:15  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.54
2009 Aug 31 00:48:07  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1021-1042
2009 Aug 31 00:48:27  <aamar> wow!
2009 Aug 31 00:49:00  <aamar> oh, no -- they're the same
2009 Aug 31 00:49:06  <aamar> got confused there for a minute
2009 Aug 31 00:49:08  <aamar> 3.55 ?
2009 Aug 31 00:49:18  <inimino> looks like we put the arguments in different order
2009 Aug 31 00:49:19  <inimino> sure
2009 Aug 31 00:49:23  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1055-1060
2009 Aug 31 00:49:30  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.55
2009 Aug 31 00:51:09  <inimino> ah
2009 Aug 31 00:51:38  <inimino> I think there may be a difference in efficiency
2009 Aug 31 00:52:38  <inimino> in your (add-streams (partial-sums s) (stream-cdr s))
2009 Aug 31 00:53:24  <inimino> (partial-sums s) will need to be recalculated
2009 Aug 31 00:53:54  <aamar> interesting
2009 Aug 31 00:54:01  <aamar> I see that, agreed.
2009 Aug 31 00:54:32  <aamar> okay, see how your solution avoids that.
2009 Aug 31 00:54:34  <aamar> Cool.
2009 Aug 31 00:54:41  <inimino> ok, next one?
2009 Aug 31 00:55:47  <aamar> ok
2009 Aug 31 00:56:02  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1062-1088
2009 Aug 31 00:56:05  <inimino> this one had a very long question and very short answer...
2009 Aug 31 00:56:08  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.56
2009 Aug 31 00:56:40  <aamar> yes
2009 Aug 31 00:57:04  <inimino> and the same answer :)
2009 Aug 31 00:57:25  <aamar> I thought that this answer would be wrong, since it was so simple... but testing it made it look right.
2009 Aug 31 00:57:27  <aamar> cool
2009 Aug 31 00:57:28  <inimino> nice problem, too, I thought
2009 Aug 31 00:57:45  <aamar> 3.57 ?
2009 Aug 31 00:57:45  <inimino> 3.57?
2009 Aug 31 00:57:47  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1090-1092
2009 Aug 31 00:57:59  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.57
2009 Aug 31 00:58:23  <aamar> same answer
2009 Aug 31 00:58:36  <inimino> yep
2009 Aug 31 00:58:51  <inimino> alright, 3.58?
2009 Aug 31 00:59:05  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.58
2009 Aug 31 00:59:09  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1094-1099
2009 Aug 31 00:59:38  <aamar> liked that one, though it wasn't very hard
2009 Aug 31 00:59:51  <inimino> yeah, me too
2009 Aug 31 01:00:18  <aamar> 3.59 ?
2009 Aug 31 01:00:22  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1108-1123
2009 Aug 31 01:00:26  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.59
2009 Aug 31 01:01:00  <inimino> whoo stream-map and integers
2009 Aug 31 01:01:05  <inimino> nice solution
2009 Aug 31 01:01:27  <inimino> mine is a bit ... kludgy
2009 Aug 31 01:01:37  <aamar> thanks
2009 Aug 31 01:02:04  <aamar> looks right, though
2009 Aug 31 01:02:40  <inimino> also, scale-stream in (b) which I forgot all about until a later exercises
2009 Aug 31 01:03:16  <aamar> same here, though I went back and changed it
2009 Aug 31 01:03:19  <inimino> yeah, these all look right
2009 Aug 31 01:03:25  <aamar> yes, looks good
2009 Aug 31 01:03:29  <inimino> ah :)
2009 Aug 31 01:03:39  <aamar> 3.60 was a tough one for me
2009 Aug 31 01:03:41  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1108-1123
2009 Aug 31 01:04:07  <inimino> oh yes, this one
2009 Aug 31 01:04:14  <inimino> this one took most of the time for me too
2009 Aug 31 01:04:38  <aamar> glad it wasn't just me
2009 Aug 31 01:04:39  <aamar> :)
2009 Aug 31 01:04:58  <inimino> same solution though
2009 Aug 31 01:05:05  <aamar> Yes
2009 Aug 31 01:05:07  <inimino> yeah, I found it quite hard
2009 Aug 31 01:05:27  <aamar> It just wasn't intuitive to have one branch be recursive, the other simply be a scale-stream
2009 Aug 31 01:05:34  <inimino> had to take a several breaks and go look up power series on Wikipedia, which didn't really help that much
2009 Aug 31 01:05:41  <inimino> yeah
2009 Aug 31 01:06:24  <inimino> originally I had something symmetrical and completely wrong
2009 Aug 31 01:06:39  <aamar> basically mul-series in both branches?
2009 Aug 31 01:06:50  <aamar> It looks right at first, but quickly introduces too many terms.
2009 Aug 31 01:06:55  <inimino> scale-series in both
2009 Aug 31 01:07:03  <aamar> Ok
2009 Aug 31 01:07:16  <inimino> after I called it done and was working on the next problem I realized it had far too few terms ;)
2009 Aug 31 01:07:24  <aamar> right, similar problem
2009 Aug 31 01:07:34  <inimino> yeah
2009 Aug 31 01:07:58  <aamar> ok, should we go to 3.61 ?
2009 Aug 31 01:08:06  <inimino> ok, sure
2009 Aug 31 01:08:14  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1148-1154
2009 Aug 31 01:08:15  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.61
2009 Aug 31 01:09:33  <aamar> forgot to make it efficient again
2009 Aug 31 01:09:41  <inimino> similar answers, yeah
2009 Aug 31 01:10:04  <inimino> that and the order of calls are the only differences I see
2009 Aug 31 01:11:29  <aamar> looks otherwise the same, right
2009 Aug 31 01:11:34  <aamar> and 3.62 ?
2009 Aug 31 01:11:49  <inimino> http://inimino.org/~inimino/projects/2009/SICP/chap_3/3.62
2009 Aug 31 01:11:58  <inimino> this is the last one I finished
2009 Aug 31 01:12:08  <aamar> http://github.com/aalearn/aalearn-sicp/blob/668d7df57a8c542709dbcc920630a64ad4c6decd/ch3-outline.scm#L1156-1166
2009 Aug 31 01:13:45  <inimino> I think I wrote "scale-series" where I mean "scale-stream"
2009 Aug 31 01:14:08  <inimino> but we could have defined a scale-series to be the same, I guess
2009 Aug 31 01:15:10  <inimino> hm, I think I put the scale in the wrong place too
2009 Aug 31 01:15:11  <aamar> right, ok
2009 Aug 31 01:15:27  <aamar> I think yours will work too, though... still looking
2009 Aug 31 01:16:23  <inimino> I think my (/ 1 scale) should actually just be (scale) to cancel out properly
2009 Aug 31 01:16:37  <inimino> or rather, it should be (/ 1 scale) in both places
2009 Aug 31 01:16:59  <inimino> or better yet it should be defined as the reciprocal in the first place
2009 Aug 31 01:17:15  <aamar> just tested your code and it gives the same answer as mine
2009 Aug 31 01:17:40  <inimino> hm
2009 Aug 31 01:17:52  <aamar> we both are scaling s2 by 1/(stream-car s2)
2009 Aug 31 01:17:55  <aamar> and then inverting
2009 Aug 31 01:18:07  <aamar> and then multiplying by s1
2009 Aug 31 01:19:26  <aamar> oh
2009 Aug 31 01:19:30  <inimino> did your test have a fractional first term in the divisor?
2009 Aug 31 01:19:31  <aamar> my test is a bad one
2009 Aug 31 01:19:31  <aamar> !
2009 Aug 31 01:20:25  <aamar> no, that is the problem
2009 Aug 31 01:21:01  <inimino> :)
2009 Aug 31 01:21:11  <inimino> so I think your code is correct
2009 Aug 31 01:21:16  <inimino> and mine has the error
2009 Aug 31 01:21:43  <aamar> ok
2009 Aug 31 01:22:23  <inimino> (define (div-series s1 s2)
2009 Aug 31 01:22:23  <inimino>   (if (eq? (stream-car s2) 0)
2009 Aug 31 01:22:23  <inimino>       (error "zero constant term in denominator")
2009 Aug 31 01:22:23  <inimino>       (let ((scale (/ 1 (stream-car s2))))
2009 Aug 31 01:22:23  <inimino>         (mul-series (scale-series s1 scale)
2009 Aug 31 01:22:23  <inimino>                     (invert-unit-series (scale-series s2 scale))))))
2009 Aug 31 01:22:29  <inimino> I think that's corrected
2009 Aug 31 01:23:47  <aamar> This should produce tangent, correct?
2009 Aug 31 01:23:48  <aamar> (div-series (scale-stream sine-series 1/5) (scale-stream cosine-series 1/5))
2009 Aug 31 01:24:13  <aamar> (sin/5)/(cos/5) ?
2009 Aug 31 01:24:52  <inimino> why the 1/5?
2009 Aug 31 01:25:19  <aamar> just so it's a better test of the scaling factor
2009 Aug 31 01:25:26  <inimino> oh
2009 Aug 31 01:25:34  -*- inimino has a short attention span
2009 Aug 31 01:25:38  <aamar> ok, just checked it.
2009 Aug 31 01:25:56  <aamar> checked the new code you just put in here, it does give the right power series for tan
2009 Aug 31 01:26:02  <inimino> yeah it should produce tan
2009 Aug 31 01:26:09  <inimino> ok, good
2009 Aug 31 01:26:53  <inimino> alright, I guess that's all for today since that's as far as I got
2009 Aug 31 01:27:01  <inimino> what should we aim for next time?
2009 Aug 31 01:27:37  <aamar> Well, I only got a little further, but the next few were fairly quick
2009 Aug 31 01:28:04  <aamar> 20 exercises would get us to the end of chapter 3
2009 Aug 31 01:28:29  <aamar> we got through 16 this time, so that's pretty aggressive if there are some tough ones ahead
2009 Aug 31 01:28:43  <aamar> 3.76 ?
2009 Aug 31 01:28:57  <inimino> true
2009 Aug 31 01:29:20  <inimino> alright, 3.76 sounds good
2009 Aug 31 01:29:27  <aamar> great
2009 Aug 31 01:29:54  -*- inimino really should learn to spread the work over more days ;-)
2009 Aug 31 01:30:04  <aamar> same here!
2009 Aug 31 01:30:12  <inimino> heh
2009 Aug 31 01:30:53  <inimino> alright, so Sept 13, 3.63 - 3.76
2009 Aug 31 01:36:09  <inimino> see you next time :)
2009 Aug 31 01:36:17  <aamar> see you!