Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Ruby Programming Language

[QUIZ] FizzBuzz (#126) [solution #1]


I've got two solutions this go-round.  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 non-tiny 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 non-tiny 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 mod-15 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

  signature.asc
1K Download

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 non-tiny 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, 2007-06-07 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

  signature.asc
1K Download

On Thu, 2007-06-07 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

  signature.asc
1K Download

On 6/7/07, MenTaLguY <men@rydia.net> wrote:
> On Thu, 2007-06-07 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, 2007-06-07 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 two-argument 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

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc