Post
Post #0 (isolation #0) » Mon Dec 24, 2018 7:53 pm
Postby Plotinus »
Newbie 1909 | Scheme
Hello. In this game I'll be introducing a computer language called Scheme, which has a very simple syntax that you can learn in a couple days. If you're using Linux you may already have Guile installed, in which case you're good to go. If you're on another system you might want to try another interpreter/compiler. Such as Ikarus for OSX or Chez Scheme on Windows
- Don’t be a dick. This is a heated game but toxicity will not be tolerated. Attack the play not the player. If your fellow players tell you to stop, you must stop. If you do not stop, I will tell you to stop. If you still do not stop, you will be force-replaced. Asking people to stop voting you or to stop scumhunting you entirely doesn't count for this rule and you may find yourself lynched if you try it.
Don't talk about ongoing games
- You may not talk to each other about this game outside of threads I have created for this purpose. You may not talk about other ongoing games in this thread.
Animated GIFs
- are of the devil, but they are permitted behind spoilers if clearly labelled as such.
Tiny text
- is also of the devil, keep it 70+ please.
Provable randomness
- is against the rules. Saying that you rolled a dice is fine, using dice tags or random.org is not.
Claiming scum
- by yourself is fine. Claiming scum with another player is against the rules.
- You have about 72 hours to confirm your role and your alignment by PM. Game will start sooner if everyone confirms. Posting in a private topic counts as confirmation.
Days
- Day 1 lasts 10 days and other days last 7 days. Extensions may be granted if there are replacements, or if the majority of players make it clear to me that an extension is desired.
Activity
- You must post at least once every 36 hours or I will Prod you. You then have 24 hours to post in the game thread or I will replace you. If you come back before I find a replacement, you can stay. The activity timers run at half-speed on weekends. Players can request me to prod somebody early. This will only count as an official prod if you don't post before you would have been due for a prod. If you haven't posted in the 24 hours before the thread is locked for night, you must reply to the night start PM or you will be replaced during the night.
Vacation/Limited Access
If you need to be absent for longer than this, you should declare
V/LA
in bold in the thread like this: [
b]
@Mod: I will be v/la until Thursday
[
/b]. While you are V/LA, you will be nudged once every 54 hours. Two nudges equals one prod. If you have not posted game advancing content in 5 days, regardless of V/LA status, you will be replaced.
Prodging
- A naked "prod dodge" does not reset the prod timer. To avoid being prodded/replaced for inactivity, include some game advancing content in your prodges, such as "got prodded; xxxx is still scum."
Quoting
- You may not quote (or copy paste) any private information into the thread, including your role PM and any mod communication.
Voting
- Votes must be in bold in the format VOTE: Plotinus or
Vote: Plotinus
. Strong preference for using vote tags instead of bold tags. Unvotes are nice but not required. If I think it’s a vote, it’s a vote, no tricks. Type [
v]Plotinus[
/v] to vote and [
uv]Plotinus[
/uv] to unvote.
Lynching
- Days end early when a simple majority of players (50% of living players + 1 rounded down) vote to lynch somebody. If a majority is not reached at deadline or if a majority of the players vote for no lynch, the day will end without a lynch. At evens, 50% is sufficient for no lynch.
Twilight
- Begins when a majority is reached and lasts until I lock the thread. You're still alive until I flip you so you can talk in any game threads you have access to until then, but no votes or unvotes will be counted.
Night
- Night lasts at least 48 hours. The night phase can be shortened if every living player -- even those with no night actions -- agrees to it and if I'm not busy.
Action submissions
- You may submit actions via PM (if town) or PT (if scum). If the actions are not submitted by the deadline then you do nothing. You can change your mind as many times as you like before the deadline.
Reminders
- If I don't hear from you about your night actions, I'll PM you 24 hours before the deadline. This doesn't count as a prod. If I still don't hear from you, you will take no action.
Play to win
- this particular game, not some future one, and keep it fun!
Each Newbie Game will be given a setup that incorporates one mafia role from the top of a column, and then two town roles from a row below the selected mafia role. The remaining six roles will be filled in by
Post
Post #3 (isolation #3) » Mon Dec 24, 2018 8:36 pm
Postby Plotinus »
All role PMs have been sent out (in the order of the signup list so timestamps mean nothing)! We will start in (expired on 2018-12-27 08:45:00) or when [8/9] people have confirmed, whichever happens sooner.
The above clock and any others used throughout this game will be accurate from the time you loaded the page.
Post
Post #4 (isolation #4) » Mon Dec 24, 2018 10:19 pm
Postby Plotinus »
At least one person wants to know if you need to download anything to play this game. The answer is no. In newbie games, and most other games on this site, the flavour is just for fun and you can ignore it entirely. Even in theme games, we try to make them playable to people who don't care about the flavour.
If you're not interested in learning an obscure programming language, then don't install anything and when reading the vote counts, just scroll down to the part outlined in red. That's where the votes will be.
Post
Post #5 (isolation #5) » Wed Dec 26, 2018 8:45 pm
Postby Plotinus »
Scheme is a dialect of Lisp, which stands for Lost In Stupid Parentheses. Just kidding, it stands for LISt Processor. Any good text editor can automatically make the parentheses be different colours so you don't get lost.
In Scheme, everything has something that it is and something that it does. For example,
+
is a procedure named
+
. It takes an optional amount of numbers, and what it does is add those numbers together. When you're writing your own procedures, it's important to give them really obvious names like
+
so that it's obvious what your procedure actually does.
This tells me that + is a procedure named + that takes an optional list of operands, and that 1 and 2 are (integers) named 1 and 2.
If I want to learn the sum of 1 and 2, I need to put it in parentheses. An open parentheses means "evaluate this procedure" and a close parentheses shows Scheme where the procedure and its operands ends.
You now know almost everything you need to know about scheme's syntax: Open parentheses: evaluating a thing. Lack of parentheses: referring to the thing by name.
You might notice that the command is
(+ 1 2)
not
(1 + 2)
. This is called Polish notation and it means the procedure always goes first and then everything after that are the things the procedure is working on. A benefit of Polish notation is that instead of writing
(2 *
(1 + 2 + 3 + 4 + 5 + 6)
)
you can write
(* 2
(+ 1 2 3 4 5 6)
)
.
Mod notes:
Good luck everyone!
Water Guard and Cyndiac never opened the role PMs I sent them. They are replaced by ZombieStriker and Dell respectively.
ZombieStrikes and Dell have another (expired on 2018-12-29 08:45:00) to confirm before they too will be replaced.
Please take a moment to familiarise yourselves with my ruleset because I have some rules you may not have encountered in other games before regarding animated gifs, tiny text, prodging and perhaps some other things.[/area]
Post
Post #25 (isolation #7) » Thu Dec 27, 2018 8:03 am
Postby Plotinus »
In Scheme, we have a way to define a procedure or a variable. The procedure for this is called
(define)
scheme@(guile-user)>
(define players 9)
scheme@(guile-user)> players
$1 = 9
So I have created a variable, named it players, and set its value to be a pointer to the concept of nineness, which is represented by the symbol 9, which is built in Scheme. We didn't have to
(define 9
(+ 1 1 1 1 1 1 1 1 1)
)
ourselves. This means that 9 is a primitive: something the language already knows that we don't have to teach it.
In practice, for speed, integers don't take up a lot of space and so the compiler has an optimisation to just write the bytes into the variable itself rather than use a pointer, but you don't have to worry about that programmatically; you can conceptualise it in your head that everything is a pointer and thinking about it like this won't lead you astray.
We can also define a procedure like this:
(define
(square x)
(* x x)
)
Notice that
(square x)
is surrounded by parentheses. This means that
square
is a procedure, not a variable.
x
is the variable that
square
operates on. The next set of parentheses defines what it does:
(* x x)
- it returns the product of x and x.
If we type it into the interactive prompt, it gives us the answer immediately: scheme@(guile-user)>
(square 361)
$3 = 130321
What happens if we leave off the parentheses? In the case we are asking it dereference the pointers (e.g. "Saying what is that?") that are in
What is square? It is a procedure named square that works on a variable x. What is 361? It is the number 361.
Remember that parentheses mean "evaluate the procedure" and lack of parentheses mean "dereference the pointer".
When I first started playing with scheme I spent a while wondering how to get a procedure to return something. The answer is quite elegant: a procedure always automatically returns the obvious thing for it to return. In our procedure
(square x)
, we returned the product of x and x.
In the interactive prompt, it's understood that you'll just be playing around, so it is okay to do this:
is for creating a variable-or-procedure out of nothing and allocating memory for it. It is not for renaming things. We might get to variable reassignment later but you'd be surprised how many things we can do without it.
Mod notes:
ZombieStrikes and Dell have another (expired on 2018-12-29 08:45:00) to confirm before I start looking for a replacement.[/area]
Post
Post #52 (isolation #8) » Thu Dec 27, 2018 10:31 am
Postby Plotinus »
We defined square in the last votecount.
(define
(square x)
(* x x)
)
Now we can use it just the way we would use * or +, nested to arbitrary levels of depth like:
(square
(square
(square
(square
(square 4)
)
)
)
)
18446744073709551616
And we can use it in new procedures like:
(define
(difference-of-squares x y)
(-
(square x) (square y)
)
)
What really happens when we type
(difference-of-squares
(square 5) (square 4)
)
?
Well, first it expands it out:
(difference-of-squares
(* 5 5) (* 4 4)
)
And then it expands it out again:
(difference-of-squares 25 16)
And then it puts 25 and 16 into the body of the procedure like this:
(-
(square 25) (square 16)
)
And again:
(-
(* 25 25) (* 16 16)
)
And again:
(- 625 256)
And finally returns the answer:
369.
This is called eager evaluation and most programming languages use it. But it isn't the only way of doing things. It could substitute like this instead:
Post
Post #111 (isolation #9) » Thu Dec 27, 2018 8:20 pm
Postby Plotinus »
Someone mentioned Python. I'm a python programmer too, but learning scheme is helping me become a better python progrmamer because I'm understanding concepts that I never really got before.
In programming you often want to test whether something is true, and if it is do one thing, if it's not, do something else. One way to do that in Scheme is with the procedure if.
So let's write a fibonacci program.
(define
(fibonacci n)
(if
(<= n 1)
n
(+
(fibonacci
(- n 2)
) (fibonacci
(- n 1)
)
)
)
)
What this says is: Define fibonacci n to be a procedure such that if n is less than or equal to 1, return n, otherwise return the sum of the fibonacci of the difference between n and 2 and the fibonacci of the difference between n and 1.
So if I type in (fibonacci 4), this is what it's doing internally:
4 is not less than equal to 1, so
(+
(fibonacci 2) (fibonacci 3)
)
2 and 3 are not less than equal to 1 so
(+
(+
(fibonacci 0) (fibonacci 1)
) (+
(fibonacci 1) (fibonacci 2)
)
)
0 and 1 are less than equal to 1 so we're finally returning some values rather than more recursion:
(+
(+ 0 1 ) (+ 1
(+
(fibonacci 0) (fibonacci 1)
)
)
)
Almost there:
(+ 1
(+ 1
(+ 0 1)
)
)
And you can see that this is going to return 3.
Recursion is really easy in Scheme! It's harder in Python, which doesn't support tail call optimisation. This function doesn't use tail-recursion either because its tail call is to + not to fibonacci but you guys need a vote count.
Mod notes:
ZombieStrikes and Dell have another (expired on 2018-12-29 08:45:00) to confirm before I start looking for a replacement.
I mean I like to live dangerously and all but I feel that was too much and proving a point???? I’m past useful today but we should make sure there is a tomorrow et al.
If it looks like a vote, it is. The automated vote counter doesn't care what is inside the unvote tag, but even if it did, I'd edit the post to help the vote counter understand it. For an example of something the automated vote counter doesn't understand:
Hypothetical player wrote:VOTE: unvote
For the automated vote counter: UNVOTE: --P
[/area]
Last edited by Plotinus on Thu Dec 27, 2018 11:25 pm, edited 1 time in total.
Post
Post #125 (isolation #10) » Fri Dec 28, 2018 6:05 am
Postby Plotinus »
Sometimes you need to be able to go in more directions thans just left or right. That's where
(cond)
itionals come in. You can set up any number of conditions. You don't have to use
if
at all if you don't want to, because you could just as easily make a cond with two conditions. Factorial is only defined for integers >= 0 but wouldn't it be fun if we could have negative factorials too? What would that look like?
(define
(extended-factorial n)
(cond
(
(= 0 n)
1)
(
(= 1 n)
1)
(
(= -1 n)
-1)
(
(> n 1)
(* n
(extended-factorial
(1- n)
)
)
)
(else
(* n
(extended-factorial
(1+ n)
)
)
)
)
)
I could combine the first two conds with an or but I haven't introduced or to you guys yet, and this is readable enough.
So first it checks if n is 0. If it is, it returns 1 because wikipedia says that is how 0! is defined.
If n is not 0, it checks if n is 1. if it is, it returns 1.
If n is neither 0 nor 1 it checks if n is -1. If it is, it returns -1.
If n is greater than 1, it returns the product of n and extended-factorial of the decrement of n.
(1-)
is a procedure called decrement that takes an operand, x, and returns x - 1. It doesn't return "1 - x".
If all those things are false, then n is less than -1. So instead of
(else)
I could have written
(
(< n -1)
)
, so return the product of n and the extended-factorial of the increment of n.
(1+
is a procedure called increment that takes an operand, x, and returns 1 + x. I ran into increment before I ran into decrement and was briefly confused that (1+ x) didn't look like polish notation, but spacing is important here. 1+ is a procedure that happens to add one to something.
If you wanted to make life harder for your future self who has forgotten how your program works, you could write a procedure like this:
(define
(1+ x)
(+ 2 x)
)
This terrible procedure wouldn't affect the way the + procedure works at all, it'd just overwrite the increment procedure. But it would still be terrible because the program does not do what its name leads you to think that it does! Anyway (+1 and (-1 are just a bit of syntactic sugar. You could just always write
(- x 1)
and
(+ x 1)
You might have noticed that in cond we acquire an extra set of parentheses that we don't acquire with if. This is because cond is more powerful than if. With if, you can only do one thing if it's true and only one thing if it's false, so it doesn't need an extra set of parentheses to group things. With cond, we can potentially have it do a whole sequence of things, and the extra parentheses show us when that whole sequence of things is done.
Mod notes:
ZombieStrikes and Dell have another (expired on 2018-12-29 08:45:00) to confirm before I start looking for a replacement.[/area]
Post
Post #131 (isolation #11) » Fri Dec 28, 2018 9:12 am
Postby Plotinus »
Dell1, Emperor flippyNips1, and ZombieStriker1 have not posted since the game began. They have been prodded and encouraged to start playing. Dell and ZombieStriker haven't opened their role PMs yet, so they will be replaced in (expired on 2018-12-29 08:45:00) if they don't join us. This is the same unchanged timer we've had in the votecounts.
Emperor flippyNips has (expired on 2018-12-30 18:00:00) to post before I start looking for a replacement, because the prod timer runs slower on the weekends.
Post
Post #156 (isolation #12) » Fri Dec 28, 2018 7:39 pm
Postby Plotinus »
So we have factorial which multiplies a bunch of numbers together, and the silly extended-factorial i wrote that multiplies a bunch of numbers together including negative ones, and I'm sure we could find a few more uses for multiplying a sequence of numbers together.
Rather than writing out the whole thing every time, let's be smart and lazy.
(define
(product func a next b)
(if
(> a b)
1
(*
(func a)
(product func
(next a)
next b)
)
)
)
Product is a procedure that takes 4 operands: a function to operate on like
square
or
*
or something, a starting value
a
, a function to produce the
next
a, and an endpoint,
b
.
If the starting point is bigger than the ending point, we're done, so return 1, because multiplying anything by 1 does nothing.
Otherwise, return the product of (evaluating the function on a) and (the result of calling product on the next a.
Well now we can do all kinds of things:
(define
(product-squares a b)
(product square a 1+ b)
)
(product-squares 1 5) will now tell you that 12 * 22 * 32 * 42 * 52 is 14400.
We can do factorial again:
(define
(factorial-again a)
(product * 1 1+ a)
)
We can approximate pi. Scheme is super fast. 100000 iterations of this is instantaneous on my ten year old computer.
(define
(approximate-pi n)
(define
(wallis b)
(/
(square
(* 2.0 b)
)
(1-
(* 2 b)
)
(1+
(* 2 b)
)
)
)
(* 2
(product wallis 1 1+ n)
)
)
scheme@(guile-user)>
(approximate-pi 100000)
$61 = 3.141584799654507
In python, of course,
approxpi
(
100000
) causes "RecursionError: maximum recursion depth exceeded" but it takes 19 microseconds to do
approxpi
(
10)
, 188 microseconds to do
approxpi
(
100)
and 2.3 ms to do
approxpi
(
1000)
, so let's assume it continues in that fashion and that it would take 203 milliseconds to do what Scheme does instantaneously.
This isn't really a fair comparison because python doesn't have the recursion optimisations that Scheme has, but I rewrote it in an iterative form using a while loop and a counter and
%timeit
approxpi
(
100000
)
188 ms ± 774 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Spoiler: python
def
approxpi
(n):
def
square
(x):
return
x**
2
def
wallis
(b):
return
square
(
2
* b) / (
2
* b -
1
) / (
2
* b +
1
)
answer =
1
while
n >
0
:
answer *=
wallis
(n)
n -=
1
return
2
* answer
Mod notes:
ZombieStrikes and Dell have another (expired on 2018-12-29 08:45:00) to confirm before I start looking for a replacement.[/area]
Post
Post #177 (isolation #16) » Sat Dec 29, 2018 5:59 am
Postby Plotinus »
Well we don't want always to find products. Sometimes we want to find sums. Also we did it recursively last time so let's do it iteratively this time. Recursion has two meanings in computer science and I don't want to confuse them. The first meaning is a procedure which calls itself. In that sense, all the procedures I've shown you have been recursive. For-each does exist in Scheme but it'll be many votecounts before I introduce it because we won't use it until we really need it and we don't need it yet.
The other meaning of recursion is a process that grows horizontally instead of just linearly. If you drew out all the evaluation steps it makes a kind of triangle, which the things it's holding in memory getting bigger and bigger. Imagine that Harry wants to add 4 and 7 so he gives the 4 to George and then George remembers 1 and hands a 3 to Fred, who remembers 1 and hands a 2 to Edith, who remembers 1 and hands a 1 to Dorothy, who remembers 1 and hands a 0 to Cathy, and then they pass the ones back up the line, adding them onto the 7 one at a time until you get 11.
So here is an accumulator that grows linearly. Because the only recursion is in a tail-call (the very last thing that iter-accumulate calls is itself), the compiler recognises that this is happening and doesn't keep the last iteration in memory, so the stack doesn't grow with each iteration, it doesn't take up more and more memory.
Accumulate takes a lot of arguments. Combiner will tell it whether we're doing products, sums, or something else. null-value is to help it get started: adding 0 or multiplying by 1 or something. If it doesn't need to do any iterations at all, this is what'll return. func is the same thing it was last time, a function that we're iterating over. When we were approximating pi it was (2n/(2n -1)) * (2n/(2n +1)). this-a is the current number that it's looking at. next-a is a function that tells it how to get to the next-a. last-a is our end point. In the internal function, answer is where we keep track of what we've figured out so far.
(product func a next b)
(accumulate * 1 func a next b)
)
And summations like this:
(define
(sum func a next b)
(accumulate + 0 func a next b)
)
factorial now looks like:
(define
(factorial n)
(product + 1 1+ n)
)
sum of squares is now just
(define
(sum-squares a b)
(sum square a 1+ b)
)
And it's lightning fast. This is the biggest number that doesn't make a noticable delay on my ancient computer, and by unnoticable I mean < 100 miliseconds.
Post
Post #202 (isolation #17) » Sat Dec 29, 2018 9:36 am
Postby Plotinus »
Well the accumulator is nice but maybe we don't want all the sums of squares, maybe we just want the sum of the squares of prime numbers, or the product of the odd numbers.
In Scheme, procedures that produce a boolean often end in a ?. the built-in procedure "odd?" returns #t if a number is odd and #f if a number is even. Isn't that charming?
So now we can have:
(define
(sum-odd-nums a b)
(filtered-accumulate odd? + 0 + a 1+ b)
But let's make some more complicated filters. Let's make a prime test. (modulo) gives you the remainder when you divide a by b. If it's zero, they divide evenly:
(define
(prime? a)
(define
(iter-guess guess)
(cond
(
(< a 2)
#f)
(
(>
(square guess)
a)
#t)
(
(= 0
(modulo a guess)
)
#f)
(else
(iter-guess
(1+ guess)
)
)
)
)
(iter-guess 2)
)
Now we can just
(define
(sum-squares-primes a b)
(filtered-accumulate prime? + 0 square a 1+ b)
Post
Post #265 (isolation #18) » Sat Dec 29, 2018 7:35 pm
Postby Plotinus »
Suppose we want the product of all positve integers less than n that are relatively prime to n. Relatively prime is just
(define
(relatively-prime? a n)
(= 1
(gcd a n)
)
)
What's gcd? We can use stein's algorithm:
(define
(gcd a b)
(define
(stein a b)
(cond
(
(= a b)
a)
(
(even? a)
(stein
(/ a 2)
b)
)
(
(even? b)
(stein a
(/ b 2)
)
)
(
(>= a b)
(stein
(/
(- a b)
2)
b)
)
(else
(stein
(/
(- b a)
2)
a)
)
)
)
(if
(and
(even? a) (even? b)
)
2
(stein a b)
)
)
So far so good but remember that the filter in accumulate takes 1 argument and our relatively-prime? takes two. What should we do? Should we rewrite the function to make it even more complicated? Currying to the rescue! Currying is a way of making a function take 1 argument when it needs more than one, by providing one of the arguments for it with a helper function. In this case, curried-relatively-prime? inherits the value of n from the scope of its parent function, so it's straightforward to create a filter that our accumulator can understand.
Currying is one of those computer science concepts that I never understood the purpose of until basically right now when I started messing with scheme and suddenly found a use for it.
(define
(product-relatively-prime n)
(define
(curried-relatively-prime? a)
(relatively-prime? a n)
Post
Post #288 (isolation #19) » Sun Dec 30, 2018 7:01 am
Postby Plotinus »
When I first ran across lambdas in python, a decade or so ago, I didn't get them. Why can't I just use
def
ine? Why do I need an anonymous function when I could just give my function a name and reuse it later? I found the syntax for them confusing. And then a few weeks ago I found myself wishing I could make a dictionary of one liner functions to be passed as arguments to bigger functions and remembered something about lambdas.
Suppose we want to make a function that approximates the integral of a function x from a to b for a given dx. We can use the
(sum)
function that we wrote before for this, because an integral is dividing a thing into a bunch of tiny pieces and then summing the tiny pieces. If you remember the sum function needs a way to get from one tiny piece to the next. We could write a little helper function like
(define
(integral-helper x) (+ x dx)
)
but then we have this little dinky function cluttering up our namespace. It's a lot simpler to just use an anonymous function here, with lambda. lambda is a primitive expression that generates a function.
We could do everything with lambdas if we wanted to, and (define (some-function)) is actually just syntactic sugar for lambda. You could write
(define add
(lambda
(x y) (+ x y)
)
)
instead of
(define
(add x y) (+ x y)
)
. Read it like "Define add to be the function of x and y that adds x to y".
Okay so now let's write our little integral function. We'll use the trapezoidal rule for taking integrals.
(define
(integral f a b dx)
(*
(/ dx 2)
(+
(f a)
(* 2
(sum f a
(lambda
(x) (+ x dx)
)
(- b dx)
)
)
(f b)
)
)
)
dx if you remember means delta x, the change in x, or how big the little pieces we've divided this thing into. If we weren't approximating an integral, we'd be taking the limit as dx approaches zero, adding up pieces of almost-zero width. But in our approximation we can set dx to be 0.00001 or whatever.
In English: Define the integral of a function f from a to b dx to be the product of dx/2 and these three things: f(a), f(b), and 2 times the sum of f from a to b - dx. To get from number in the series to the next, we add dx to x.
Post
Post #304 (isolation #20) » Sun Dec 30, 2018 8:46 am
Postby Plotinus »
One thing lambdas let us do is define some variables in an extremely local scope. If I write
(lambda
(x) (* x x)
)
, that x only exists for the duration of that lambda and after that it's gone. If I write x somewhere else, it can mean something else. So if you want to write a little helper function inside a function to hold onto a few variables for just a little while, lambda is useful for that.
So useful, that they made an easier way of doing that, called let. The syntax for let is:
(let
(
(<var1> <exp1>)
(<var2> <exp2>)
(<var3> <exp3>)
)
<body>
)
So what are all these parentheses? The outer ones, the red ones, define the boundaries of the let. The first red ( says that we're calling a procedure, named let, and the final red ) says that the procedure is over, all the variables defined therein are garbage and don't exist anymore. The orange ones show where the variables are going to be defined. The first orange ( says we're starting defining variables now, and the last orange one says we're done definine variables and now we're going to do some things with them. Finally, the inner ones, the yellow ones, are so that each variable gets their own space and we always know where one ends and the other begins.
Since a let is basically a lambda expression with some extra conveniences, you can also give them a name and then it works basically like a temporary named define that goes away when the let is over.
So suppose we want to approximate 1/φ with a truncated continued fraction. You know the kind that go:
They continue on infinitely but we don't have infinite ram so we'll truncate it at some value k and get a partially correct answer. A number like 10 or 15 works pretty well here, you don't need to go that deep to approximate 1/φ.
(define
(cont-frac numerator denominator k)
(let loop
(
(counter 0)
)
(if
(> counter k)
numerator
(/ numerator
(+ denominator
(loop
(1+ counter)
)
)
)
)
)
)
In English: define a continued fraction with a numerator, a denominator, and some k, indicating the number of levels deep we're going to be:
let there be a loop with a counter that starts at 0. Loop doesn't mean anything to Scheme's compiler, it's just a name we're giving it to describe what it does.
The body of the loop starts here:
If the counter is greater than k, we're done, so put one final numerator in onto this thing.
Otherwise divide the numerator by the sum of the denominator and the result of jumping back to the start of the loop with an incremented counter
So round 1 we have (numerator / (denominator + i-don't-know-yet))
round 2 we have (numerator / (denominator + (numerator/(denominator + i don't know yet)))
round 3 we have (numerator / (denominator + (numerator/(denominator + (numerator/denominator + i don't know yet)))
...
round k we have (numerator / (denominator + (numerator/(denominator + (numerator/denominator + (...(numerator/(denominator+ numerator))))))))))
and then it's just some adding and dividing, which computers are good at and it spits out an answer for us. yay!
Post
Post #324 (isolation #21) » Sun Dec 30, 2018 7:58 pm
Postby Plotinus »
Dicideaq1 has been prodded. They have (expired on 2019-01-01 07:55:00) to post before I start looking for a replacement. This prod is about 4 hours late because I am just waking up. teacher has the algorithm right but I think he was counting in UTC instead of UTC+1. When we were on 48 hours prods I was able to do the weekends halftime math in my head but I just couldn't get used to the 36 hours shedule so I wrote a script for it.
Post
Post #325 (isolation #22) » Sun Dec 30, 2018 7:58 pm
Postby Plotinus »
In computer science, a quine is a program that when you run it, it outputs its own sourcecode. In some languages they're difficult to construct. but in Scheme it is quite easy. The output of a file helloworld.scm containing only the text "Hello World" will output "Hello World" because a quoted string is self-evaluating. It both is, and contains, the string "Hello World".
We'll get back to recreational mathematics in the next vote count but I am preparing this before I go to bed in anticipation that it should be posted right when I wake up.
Post
Post #350 (isolation #23) » Mon Dec 31, 2018 9:09 am
Postby Plotinus »
In Scheme, procedures are first class objects. This means that a function can return another function. A function can take a function as its arguments. A function can be stored in a list of functions. Functions can be named (with define) or anonymous (with lambda). Functions can be nested within each other, creating closures - binding variables within the scope of the function. We can use currying to reduce the arity of a function (make it require fewer arguments.)
A silly example that lets us do several of those things with funtions:
(define
(double procedure)
(lambda
(x) (procedure
(procedure x)
)
)
)
So what does this do? Well it's a function that takes a procedure of some argument x and returns another function that applies the procedure twice to x.
(
(double 1+)
3)
results in 5. (add one to three twice). It is the same as typing
(1+
(1+ 3)
)
(
(double cube)
3)
results in 19683. Cube the cube of 3. It is the same as typing
(cube
(cube 3)
)
where cube is defined as
(define
(cube x) (* x x x)
)
These days it's not that exciting that a language supports first-class functions. C doesn't. Ruby doesn't allow nested functions but supports the other things. Fortran doesn't support anonymous functions. Java only partially supports first class functions. But Scheme's support for first class functions is probably part of why it has survived as a usable language in spite of being 43 years old. For example aisleriot, gnome's solitaire game that supports 88 varieties of solitaire, is written in Scheme and GIMP's extensions are written in Scheme. We've been looking at the basic building blocks, but there are libraries for running a web server or building gtk applications.
Post
Post #375 (isolation #25) » Mon Dec 31, 2018 7:50 pm
Postby Plotinus »
Well we've been having fun with math but the only data structure we've seen so far has been an integer. And procedures I guess. But for most things we're going to need some way of
cons
tructing data types, a way of putting two things together.
The syntax for this is
(cons x y)
and what it does is create a pair that looks like
(x . y)
. Pairs are useful for all kinds of things. An imaginary number might be the cons of the real and imaginary parts. A pixel on your screen might be the cons of the x and y coordinates. We'll do some more with cons later.
Post
Post #376 (isolation #26) » Mon Dec 31, 2018 7:59 pm
Postby Plotinus »
mafia goon.
It is now Night 1. Deadline for night actions is (expired on 2019-01-03 08:00:00)
As per rule 12, anyone who hasn't posted in the last 24 hours (Emperor flippyNips) must contact me at some point during the night phase so I know they are still playing. Otherwise they will be replaced and night will be extended.
We can do a shortened night phase if everybody wants that. I need to hear from everybody, though, whether or not you have a night action. If you want short night, reply to the night start PM I'm about to send out with a yes.
Post
Post #378 (isolation #28) » Wed Jan 02, 2019 8:00 pm
Postby Plotinus »
So now that we know how to make a pair with (cons x y) it stands to reason that we should be able to extract the x or the y from the cons cell. (car (cons x y)) returns x and (cdr (cons x y)) returns y. The names are for historical reasons; on the very first lisp machine they stood for "contents of the add register" and "contents of the decrement register" but now they just mean "the head of the pair" and "the tail of the pair".
Post
Post #400 (isolation #29) » Thu Jan 03, 2019 2:33 am
Postby Plotinus »
It's really useful being able to group things together into pairs. It would be even more useful if we could somehow link more than 2 things together into a list. Does a language derived from a language called LISt Processer have such a thing?
The syntax for it is
(list x y z)
and the notation for explaining that list can take an arbitrary number of objects is actually
(list x . y)
which looks like a pair, but you'll see why y is standing in for an arbitrary number of things in a second.
(list)
is a bit of syntactic sugar. We could just write:
(cons a
(cons b
(cons c
(cons d e)
)
)
)
to generate a list (a b c d e).
Why are these two things the same? To answer this, we need to look at what list actually does.
This is a linked list. A linked list is a bunch of pairs. The car of each pair is a pointer that points to (the memory location of) some object, in this case a string, but it could be pointing to a procedure or a number or anything at all. The cdr of each pair is a pointer that points to the (memory location of the) car of the next item in a list. You don't have to know what the memory location is; that's figured out for you internally. The cdr of the item in the list links to the null list,
'()
, which is just an empty list whose value is null (or nil in lisp), and is a signal that the list is over.
Scheme, and lisps in general provide a lot of abbreviations for working with lists. We'll look at some of them today.
(car
("Alice" "Bob" "Carol" "Daniel" "Edith")
)
"Alice"
(cdr
("Alice" "Bob" "Carol" "Daniel" "Edith")
)
("Bob" "Carol" "Daniel" "Edith")
(cadr
("Alice" "Bob" "Carol" "Daniel" "Edith")
) ; the car of the cdr
"Bob"
(cddr
("Alice" "Bob" "Carol" "Daniel" "Edith")
) ; the cdr of the cdr
("Carol" "Daniel" "Edith")
(caddr
("Alice" "Bob" "Carol" "Daniel" "Edith")
) ; the car of the cdr of the cdr
"Carol"
And so on, four levels deep. If we had a multdimensional list like ((1 2) (3 4) (5)) then you might need to talk about the caar to get the car of the car or I think cadadr would get the 4 out of the list.
In practice you should be able to use simple recursion to only have to work with the car and the cdr.
If you want to work with linked lists then lisps are pretty good at that. If you really want an array then you might prefer to work in a language where your arrays don't have to be disguised linked lists. Things that are linked lists in real life: Trains, chains, strings of holiday lights, conga lines.
Things that are not linked lists in real life: cats, doorbells, pizza.
Post
Post #425 (isolation #30) » Thu Jan 03, 2019 7:48 pm
Postby Plotinus »
We might want to use cons to represent rational numbers, like 3/4. That way instead of having to keep track of a separate numerator = 3 and denominator = 4 we could keep track of just one number, (3 . 4). But we should simplify improper fractions. If we a number like -19/95 then we want to store it as 1/5.
For this I'm going to write a helper function called xor. Xor means exclusive or. xor(x y) is true if only one of x or y is true. if both are true, xor(x y) is false. if both are false, xor(x y) is false.
Post
Post #450 (isolation #31) » Fri Jan 04, 2019 10:28 am
Postby Plotinus »
I want to go back a bit and talk some more about pointers. You saw in the box diagram in the last vote count that a linked list is basically a collection of cons cells, of pairs, and the car of each pair points to a piece of data, like the string "Alice" and the cdr of each pair points to the car of the next pair in the list. So what does it mean that these are pointers? How is it different from there just be a chain like [Alice]->[Bob]->[Carol]->[Daniel]->[Edith]? What's the point?
Let's make a list of primitive operators.
(define procedures
(list + - gcd * /)
)
I threw gcd in there too even though it's not a primitive operator because remember that there's no distinction between built-in functions and the ones that we make.
What do you think happens if I type
(
(car procedures)
3 4)
?
Well let's use the substitution rule to figure out what's happening. (car procedures) evaluates to +, right? So now it's just (+ 3 4). That's why we had two sets of parentheses at the start. One to evoke car, and one to evoke whatever car returns. So we get 7.
Entering a new prompt. Type `,bt' for a backtrace or `,q' to continue.
scheme@(guile-user) [1]> ,q
scheme@(guile-user)> ((car (cddddr procedures)) 3 4)
$5 = 3/4
Okay so what's this error and why did it happen? Why didn't get cddddr get me the 5th element in the list the way caddr got me the 4th element? Remember, car gets the first item, and cdr gets the rest, cadr gets the second and the cddr gets the rest. Let's draw another box diagram.
cddddr doesn't get us / it gets us the pair (cons / '()). This '() is a list terminator, the null list, and it's getting in the way of our decision. That's why we need the car of the cddddr.
But look at this magical thing we have here, we can call a named procedure, +, or whatever, without actually using the name of the function, because + is ~really~ just a pointer to the real procedure. and (car is also returning a pointer to the procedure, so ((car follows that pointer and evaluates that procedure. This is really exciting.
Mod notes:
Keep it fun![/area]
Last edited by Plotinus on Fri Jan 04, 2019 10:34 am, edited 3 times in total.
Post
Post #481 (isolation #33) » Fri Jan 04, 2019 7:37 pm
Postby Plotinus »
Another thing about storing linked lists with pointers rather than storing the actual objects in the list is that the program can know in advance how much memory the list is going to take up, and so it knows the first address is at 0x1000 or somewhere and then maybe each pointer takes up 4 bytes, so it knows the next one is going to be at 0x1004. It doesn't have to walk through the list each time looking for the nth item, because it can just some quick math to find it. Which means if you'Re optimising your algorithm you can consider accessing an item in a list as taking a constant amount of time, because your CPU can execute that command in a single action.
Suppose lists weren't like that. What if we were storing our data in some xml tree where the items could be as big as they are and who knows how big the next row is? well then the only way to find something is to traverse the tree and it takes a lot longer and that's why xml is slow.
Post
Post #482 (isolation #34) » Fri Jan 04, 2019 7:40 pm
Postby Plotinus »
Amzela1 and Child1 have been prodded. They have (expired on 2019-01-07 03:50:00) to post before I start looking for a replacement, because the timer runs slower on weekends.
Post
Post #518 (isolation #36) » Sat Jan 05, 2019 12:09 pm
Postby Plotinus »
There are a lot of built-ins for dealing with lists, but it is interesting to consider how one might implement them. For example there is the (last-pair ) which will tell you the last item in a list.
suppose we have a list of numbers, (1 2 3 4 5) and we don't know how long it is. All have is a pointer to the start of the list and then the list is as long as it is. Who knows where it is. How do we find the last item?
The only way is to walk through the list and check if each item is the last. How will we know when we get there? The cdr of the list will point to null rather than to a new item. This is just exactly the way strings work in c, except with lists. and they don't call them cdrs.
We don't know how long our list is, but we can use recursion to make the problem smaller and smaller until we have something we know how to solve. Suppose we had a list and we checked the cdr of it and we got null. That would mean we'd found our answer right away, that the list had only one element, that the first item was the last item. So we just return the last item and then we're done.
Suppose we have a list and we check the cdr of it and it is not null. That means we haven't found our answer yet, so let's do the same operation again on the cdr of the list, which is necessarily one element shorter than the first list. In this example we'd be looking at the list (2 3 4 5), then the list (3 4 5), then the list (4 5), then the list (5) and oh hey the cdr of that is null so that must be the answer!
(define
(my-last-pair lis)
(if
(null?
(cdr lis)
)
lis
(my-last-pair
(cdr lis)
)
)
)
What is the algorithmic complexity of this algorithm? If n is an arbitrarily large number, like 1000000, how much longer will it take than if n is 10? How much memory will it take up while it's doing its computations?
Each pass, it does these operations:
1) follow a pointer to the cdr of the list
2) check whether the cdr is null
3) return an answer or call itself with a smaller list
We can assume that each of these basic operations takes a constant amount of time, perhaps 1 nanoseconds each. So it's time complexity is going to grow linearly. If n is one then it does 3 things in 3 nanoseconds. If n is ten then it does 30 things in 30 nanoseconds . If n is a million then it does 3 million things in 3 miliseconds . Linear growth, growth by a factor of n, is written as O(n), and it is pretty good. The only thing better would be constant time, if we just knew the answer without having to look it up and then it would take 1 nanosecond to find it no matter where it was or how deep in the list. I can't think of a way to do that -- we could store the answer in a lookup table but then how do we know where it is in the lookup table without looking for it? What even is a lookup table if it's not a list?
Finding the nth item in the list is something we can do in constant time. The command for this is (list-ref index some-list) but you need to know the index for it to work. If we want the last item in the list then we have to find out how long the list is and we can only do that by walking down the list. So I think linear time is as good as it gets in practice.
What about memory? Well, remember that Scheme has tail-call optimisation, which means that if the very last thing a function does is call another function, then it doesn't have to keep the function available in the stack (in memory) because it's done; instead whatever the next function returns is going to be sent to the parent function: whatever isn't done.
So we call (my-last-pair '(1 2 3 4 5)), and it calls (my-last-pair '(2 3 4 5)) but it doesn't stick around for the answer; it doesn't care anymore. So we still have only two process running in memory: whoever started this off to begin with, and the one that is currently running. Now the new one calls (my-last pair '(3 4 5)) but it doesn't stick around the for the answer. It doesn't care anymore. It's gone. Now the new one calls (my-last pair ('4 5)) but it doesn't care about the answer either. It's gone. So finally we're calling (my-last-pair '(5)) but the process that calls it doesn't care about the answer either so that's gone too. And now we return 5. Who do we return it to? none of the processes in the middle are here anymore. We return it to whoever made that very first call, the one to (my-last-pair '(1 2 3 4 5)). Maybe it was just the user who typed it into the interactive prompt, in that case we return it to them by printing it on the screen. Maybe it was some function like (define last-one (my-last pair '(1 2 3 4 5))), so we return it to that define function, which now knows what value to assign to last-one: '(5).
So the amount of memory this function takes up is constant. Even if the list is a million items long, it never has more 2 items on the stack. The memory complexity is O(2). This means that even my antique computer will not be overwhelmed by it!
Post
Post #519 (isolation #37) » Sat Jan 05, 2019 12:11 pm
Postby Plotinus »
vanilla townie.
It is now Night 2. Deadline for night actions is (expired on 2019-01-08 08:00:00). Everyone has posted in the last 24 hours so nobody is in danger of being replaced.
We can do a shortened night phase if everybody wants that. I need to hear from everybody, though, whether or not you have a night action. If you want short night, reply to the night start PM I'm about to send out with a yes.
Post
Post #521 (isolation #39) » Mon Jan 07, 2019 8:01 pm
Postby Plotinus »
It is really common to want to do the same thing to every item in a list. The way to do this is with (map). For example (map square '(1 2 3 4)) would use our square function from earlier to produce a new list (1 4 9 16).
Mod notes:
Keep it fun![/area]
Last edited by Plotinus on Mon Jan 07, 2019 8:19 pm, edited 1 time in total.
Post
Post #527 (isolation #40) » Mon Jan 07, 2019 8:12 pm
Postby Plotinus »
foreach is like map. It's for when you want to do something with each item in a list. Print them, for example. Map is if you want to change everything in a list in the same way, foreach is if you want to use each item to do something else.
Post
Post #569 (isolation #41) » Tue Jan 08, 2019 7:37 am
Postby Plotinus »
So far we've mostly been thinking about lists in a flat way but you can build intricate structures out of linked lists, and one common structure is called a tree. On most computers, the entire file system is organised in a tree like structure. On Linux we have the root node, / which contains some branches like usr, home, bin, dev, and then each of those are nodes which contain some more branches. On Windows you have a root node like C:\ and inside it you have some branches like My Documents, My Pictures, etc. and Macs are basically the same as Linux these days.
Or in your browser, if you have a lot of bookmarks, you might start organising them a little by category so that you don't have more than a screenful in one folder. You might have a games folder or a sports folder or a news folder or a recreational mathematics folder.
So you're familiar with the idea of having folders which can contain folders which can contain folders.
The most basic kind of tree is a binary tree. Each node can contain, at most, two things, but they can have an arbitrary amount of children. You could also have ternary trees where each node has at most 3 children, and quarternary trees with 4 children. All of these words have the suffix -ary so we can talk about the arity of a tree: how many children each node can have. There was a hilarious lecture by Donald Knuth about three-halvsary trees in which each node could have 3/2 children, and he proposed that if we were to study trees that had i children we could call them imagin-ary trees.
Anyway, let's do binary trees because they're easy and important.
Post
Post #570 (isolation #42) » Tue Jan 08, 2019 7:44 am
Postby Plotinus »
This one's about how to make escher like pictures in Scheme!
emperor flippyNips has been lynched day 3. He was a
mafia rolecop
!
This means town has won Newbie 1909 | Scheme. I hope you enjoyed it! Scheme's source code is, itself, basically a linked list, which makes it particularly good for AI programming. If you're ever writing a program that needs to edit its own source code, think of Scheme. It's evolved some since 1986. You can import object oriented programming now, for example.
So congratulations to
Clemency, town neapolitan, Amzela, town doctor,
Child, EGL, Loopdan, teacher, and u r a person 2, vanilla townies.
Post
Post #600 (isolation #45) » Tue Jan 08, 2019 7:53 pm
Postby Plotinus »
The last post in teacher's thread came when Amzela was resisting claiming her role. It's worth pointing out that both scum and the hidden PR reacted the same way to this situation. I think it's a pretty natural reaction from the perspective of a PR, especially a newer player.
I think Clemency's post asking for a claim looked pretty clearly like "I have a result and I need everybody to claim so I can catch them in a lie" but of course it would be clear to me when I have the answers already. But it's something to pay attention to in future games, both as town and as scum -- think about all the possible night actions that could have affected you and see if you still have a path to win. In this case I don't think there was because scum needed two mislynches and even if you lynch the cop/tracker/jailkeeper/neapolitan today you still get lynched tomorrow. But sometimes there will be.
