




Ruby Programming Language









[QUIZ] FizzBuzz (#126) [solution #1]
I've got two solutions this goround. First, the solution I would present were I asked to do this in an actual job interview: for n in 1..100 mult_3 = ( n % 3 ).zero? mult_5 = ( n % 5 ).zero? if mult_3 or mult_5 print "Fizz" if mult_3 print "Buzz" if mult_5 else print n end puts end mental
And, here's my second one, written in a subset of Ruby which corresponds to a pure (though strict) lambda calculus, building up numbers, strings, and everything else entirely from scratch. (Okay, I cheated a little bit for actual IO) Sadly Church numerals are very slow for nontiny numbers, and Ruby doesn't do tail recursion optimization which just makes matters worse. But it does work, given enough time and stack space. Try running it and see how high you can get! mental alias LAMBDA lambda def LAMBDA2(&f) ; LAMBDA { x LAMBDA { y f[x, y] } } ; end def LAMBDA3(&f) ; LAMBDA { x LAMBDA { y LAMBDA { z f[x, y, z] } } } ; end U = LAMBDA { f f[f] } ID = LAMBDA { x x } CONST = LAMBDA2 { y, x y } FLIP = LAMBDA3 { f,a,b f[b][a] } COMPOSE = LAMBDA3 { f,g,x f[g[x]] } ZERO = CONST[ID] SUCC = LAMBDA3 { n,f,x f[n[f][x]] } ONE = SUCC[ZERO] TWO = SUCC[ONE] THREE = SUCC[TWO] ADD = LAMBDA { n n[SUCC] } FIVE = ADD[TWO][THREE] SIX = ADD[THREE][THREE] SEVEN = ADD[FIVE][TWO] EIGHT = ADD[FIVE][THREE] MULTIPLY = COMPOSE FOUR = MULTIPLY[TWO][TWO] NINE = MULTIPLY[THREE][THREE] TEN = MULTIPLY[FIVE][TWO] POWER = LAMBDA2 { m, n n[m] } A_HUNDRED = POWER[TEN][TWO] FALSE_ = ZERO TRUE_ = CONST NOT = FLIP OR = LAMBDA2 { m,n m[m][n] } AND = LAMBDA2 { m,n m[n][m] } ZERO_P = LAMBDA { n n[CONST[FALSE_]][TRUE_] } NIL_ = LAMBDA { o o[nil][TRUE_] } CONS = LAMBDA2 { h,t LAMBDA { o o[LAMBDA { g g[h][t] }][FALSE_] } } NULL_P = LAMBDA { p p[FALSE_] } CAR = LAMBDA { p p[TRUE_][TRUE_] } CDR = LAMBDA { p p[TRUE_][FALSE_] } GUARD_NULL = LAMBDA3 { d,f,l NULL_P[l][CONST[d]][f][l] } FOLDL = U[LAMBDA { rec LAMBDA3 { f,s,l GUARD_NULL[s][LAMBDA { k rec[rec][f][f[s][CAR[k]]][CDR[k]] }][l] } }] DROP = LAMBDA { n n[GUARD_NULL[NIL_][CDR]] } LENGTH = FOLDL[LAMBDA2 { a, e SUCC[a] }][ZERO] MAKE_LIST = LAMBDA2 { v,n n[LAMBDA { p CONS[v][p] }][NIL_] } LESSER_P = LAMBDA2 { m,n NOT[NULL_P[DROP[m][MAKE_LIST[ID][n]]]] } DIVMOD_HELPER = U[LAMBDA { rec LAMBDA3 do q,l,n NULL_P[l][CONST[CONS[q][ZERO]]][ LAMBDA2 do r, t AND[NULL_P[t]][LESSER_P[r][n]][CONST[CONS[q][r]]][ rec[rec][SUCC[q]][t] ][n] end[LENGTH[l]] ][DROP[n][l]] end }] DIVMOD = LAMBDA2 { m,n DIVMOD_HELPER[ZERO][MAKE_LIST[ID][m]][n] } DIVISIBLE_BY_P = LAMBDA2 { m,n ZERO_P[CDR[DIVMOD[m][n]]] } CHAR_0 = MULTIPLY[SIX][EIGHT] FORMAT_NUM_HELPER = U[LAMBDA { rec LAMBDA2 do s, n LAMBDA do qr LAMBDA2 do q, r ZERO_P[q][ID][FLIP[rec[rec]][q]][CONS[ADD[r][CHAR_0]][s]] end[CAR[qr]][CDR[qr]] end[DIVMOD[n][TEN]] end }] FORMAT_NUM = LAMBDA do n ZERO_P[n][CONST[CONS[CHAR_0][NIL_]]][FORMAT_NUM_HELPER[NIL_]][n] end CHAR_F = MULTIPLY[SEVEN][TEN] CHAR_i = ADD[A_HUNDRED][FIVE] CHAR_z = ADD[A_HUNDRED][ADD[MULTIPLY[TWO][TEN]][TWO]] CHAR_B = MULTIPLY[SIX][ADD[TEN][ONE]] CHAR_u = ADD[A_HUNDRED][ADD[TEN][SEVEN]] CHAR_NEWLINE = TEN FIZZ = CONS[CHAR_F][CONS[CHAR_i][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]] BUZZ = CONS[CHAR_B][CONS[CHAR_u][CONS[CHAR_z][CONS[CHAR_z][NIL_]]]] OUTPUT_STRING = LAMBDA do s print FOLDL[LAMBDA2 { a,e a << e }][[]][s].map { i i[LAMBDA { s s + 1 }][0] }.pack("C*") end SEQUENCE = FLIP[COMPOSE] FIZZBUZZ_HELPER = U[LAMBDA { rec LAMBDA2 do i,r NULL_P[r][ID][LAMBDA do LAMBDA2 do mult_3, mult_5 SEQUENCE[ SEQUENCE[ OR[mult_3][mult_5][ SEQUENCE[ mult_3[LAMBDA { OUTPUT_STRING[FIZZ] }][ID] ][ mult_5[LAMBDA { OUTPUT_STRING[BUZZ] }][ID] ] ][LAMBDA { OUTPUT_STRING[FORMAT_NUM[i]] }] ][ LAMBDA { OUTPUT_STRING[CONS[CHAR_NEWLINE][NIL_]] } ] ][ LAMBDA { rec[rec][SUCC[i]][CDR[r]] } ][nil] end[DIVISIBLE_BY_P[i][THREE]][DIVISIBLE_BY_P[i][FIVE]] end][nil] end }] FIZZBUZZ = LAMBDA do c FIZZBUZZ_HELPER[ONE][MAKE_LIST[ID][c]] end FIZZBUZZ[A_HUNDRED]
MenTaLguY wrote: > And, here's my second one, written in a subset of Ruby which corresponds > to a pure (though strict) lambda calculus, building up numbers, strings, > and everything else entirely from scratch. (Okay, I cheated a little > bit for actual IO) > Sadly Church numerals are very slow for nontiny numbers, and Ruby > doesn't do tail recursion optimization which just makes matters worse. > But it does work, given enough time and stack space. Try running it and > see how high you can get!
Ok, you're hired. Your first project is to write a web server in Malbolge.  vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
Incidentally, this second solution could probably be made to run in a reasonable time if the mod15 pattern in the output were exploited. But I'm lambda'd out at the moment, so it will remain an exercise for the reader. :) mental
On Jun 5, 2007, at 8:36 PM, MenTaLguY wrote: > And, here's my second one, written in a subset of Ruby which > corresponds to a pure (though strict) lambda calculus, building up > numbers, strings, and everything else entirely from scratch. > (Okay, I cheated a little bit for actual IO)
That is wild. I'm just staring at the code. I know enlightenment is hidden in there somewhere... James Edward Gray II
MenTaLguY wrote: > And, here's my second one, written in a subset of Ruby which corresponds > to a pure (though strict) lambda calculus, building up numbers, strings, > and everything else entirely from scratch. (Okay, I cheated a little > bit for actual IO) > Sadly Church numerals are very slow for nontiny numbers, and Ruby > doesn't do tail recursion optimization which just makes matters worse. > But it does work, given enough time and stack space. Try running it and > see how high you can get!
I thought it was randomly generated joke code jibberish till I copied and ran it and it worked .. slowly. So I started revising my lambda calculus till my brain hurt... So I ask a question... Using your Ruby Church numerals is it possible to test for equality? Perhapps you are doing it but I was unable to parse the whole algorithm out and figure out exactly what all the lambdas you use do. Cheers Brad
On Thu, 20070607 at 02:25 +0900, Brad Phelan wrote: > Using your Ruby Church numerals is it possible to test for equality?
Sure! EQUAL_P = LAMBDA2 { m,n NOT[OR[LESSER_P[m][n]][LESSER_P[n][m]]] } mental
On Thu, 20070607 at 02:25 +0900, Brad Phelan wrote: > Perhapps you are doing it but I was unable to parse the > whole algorithm out and figure out exactly what all the lambdas > you use do.
If it helps, what a lot of the math stuff does is create lists of the length specified by a number, manipulate those, and then count their lengths to get back to a number. For instance, subtraction would be: SUBTRACT = LAMBDA2 { m,n LENGTH[DROP[n][MAKE_LIST[ID][m]]] } (here, ID is just used as a dummy value to populate the list with) mental
On 6/7/07, MenTaLguY <men@rydia.net> wrote: > On Thu, 20070607 at 02:25 +0900, Brad Phelan wrote: > > Perhapps you are doing it but I was unable to parse the > > whole algorithm out and figure out exactly what all the lambdas > > you use do. > If it helps, what a lot of the math stuff does is create lists of the > length specified by a number, manipulate those, and then count their > lengths to get back to a number. For instance, subtraction would be: > SUBTRACT = LAMBDA2 { m,n LENGTH[DROP[n][MAKE_LIST[ID][m]]] }
must work nicely for n>m ;) But interesting stuff. Cheers Robert > (here, ID is just used as a dummy value to populate the list with) > mental
 You see things; and you say Why? But I dream things that never were; and I say Why not?  George Bernard Shaw
MenTaLguY wrote: > On Thu, 20070607 at 02:25 +0900, Brad Phelan wrote: >> Perhapps you are doing it but I was unable to parse the >> whole algorithm out and figure out exactly what all the lambdas >> you use do. > If it helps, what a lot of the math stuff does is create lists of the > length specified by a number, manipulate those, and then count their > lengths to get back to a number. For instance, subtraction would be: > SUBTRACT = LAMBDA2 { m,n LENGTH[DROP[n][MAKE_LIST[ID][m]]] } > (here, ID is just used as a dummy value to populate the list with) > mental
Thanks for the pointers. I don't have too much time today to think about this ( public holiday and I'm going out in the sun ) but I know when I do I'll want to know the concept here behind lists. Are they real lists as in Ruby Array which I doubt or abstract concepts like the Church Numerals. I'll take a look Monday and see if I can understand more. Regards Brad
On Thu, 7 Jun 2007 18:04:02 +0900, "Robert Dober" <robert.do @gmail.com> wrote: >> SUBTRACT = LAMBDA2 { m,n LENGTH[DROP[n][MAKE_LIST[ID][m]]] } > must work nicely for n>m ;) Church numerals correspond to the natural numbers, so negative results aren't possible. For n>m, I could either let the computation diverge or return ZERO  I opted to return ZERO. It is possible to build a representation of general integers atop Church numerals (one obvious way would be to use a pair consisting of a sign flag and a magnitude), but that was more than I needed for this particular problem. mental
On Thu, 7 Jun 2007 20:45:04 +0900, Brad Phelan <bradphe @xtargets.com> wrote: > Thanks for the pointers. I don't have too much time today to think about > this ( public holiday and I'm going out in the sun ) but I know when > I do I'll want to know the concept here behind lists. Lists are linked lists made of pairs, as in Lisp. Since we chose to represent true and false as twoargument functions which return their first or second argument, respectively, we can take advantage of this to describe a pair as a function which takes true or false as an argument to select an element of the pair. Such a pair can be created by a function like: MAKE_PAIR = LAMBDA2 { first, second LAMBDA { which which[first][second] } } And functions for extracting the first or second value from a pair constructed by MAKE_PAIR can be written like this: FIRST = LAMBDA { pair pair[TRUE_] } SECOND = LAMBDA { pair pair[FALSE_] } My definitions for CONS, CAR, and CDR in fizzbuzz were a little more involved, because I also needed to be able to represent an empty list (and test for it). So, what I did is roughly equivalent to: NIL_ = MAKE_PAIR[nil][TRUE_] CONS = LAMBDA2 { head, tail MAKE_PAIR[MAKE_PAIR[head, tail]][FALSE_] } CAR = LAMBDA { cell FIRST[FIRST[cell]] } CDR = LAMBDA { cell SECOND[FIRST[cell]] } NULL_P = LAMBDA { cell SECOND[cell] } A tagged data structure, basically, with a flag indicating whether a cell is a null list or not. mental
On Thu, 7 Jun 2007 20:45:04 +0900, Brad Phelan <bradphe @xtargets.com> wrote: > Are they real lists as in Ruby Array which I doubt or abstract concepts like > the Church Numerals. In some sense, these things are only as abstract as you want them to be. Instead of implementing Church numerals like this (expanded a bit for clarity): ZERO = LAMBDA2 { f,x x } ONE = LAMBDA2 { f,x f[x] } SUCC = LAMBDA { n LAMBDA2 { f,x f[n[f][x]] } } ADD = LAMBDA2 { m,n m[SUCC][n] } MULTIPLY = LAMBDA2 { m,n LAMBDA2 { f,x m[n[f]][x] } } POWER = LAMBDA2 { m,n n[m] } I could also have done something like this: class ChurchNumeral attr_reader :value def initialize(value) @value = value end def call(f) LAMBDA { x @value.times { x = f[x] } ; x } end alias [] call end ZERO = ChurchNumeral.new 0 ONE = ChurchNumeral.new 1 SUCC = LAMBDA do n if ChurchNumeral === n ChurchNumeral.new n.value + 1 else LAMBDA2 { f,x f[n[f][x]] } end end ADD = LAMBDA2 do m,n if ChurchNumeral === m and ChurchNumeral === n ChurchNumeral.new m.value + n.value else m[SUCC][n] end end MULTIPLY = LAMBDA2 do m,n if ChurchNumeral === m and ChurchNumeral === n ChurchNumeral.new m.value * n.value else LAMBDA2 { f,x m[n[f]][x] } end end POWER = LAMBDA2 do m,n if ChurchNumeral === m and ChurchNumeral === n ChurchNumeral.new m.value ** n.value else n[m] end end As described in my previous email, I did take the former sort of approach for lists though. mental





