You are currently browsing the tag archive for the ‘Computer Science’ tag.

This is a follow-up to my previous post, THIS IS NOT A REVIEW. I was inspired by a comment from Julia to translate the examples Airi and Maimi wrote (in the fictional universe depicted in my last post) into Turing, from the original Scheme.

The original snippets of code were:

**(printing “LOVE” an infinite number of times using named recursion in Scheme)**

(define (FOREVER x) (display x) (FOREVER x)) (FOREVER "LOVE ")

**(the Y combinator in Scheme)**

(lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))

**(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in Scheme)**

(((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))) (lambda (p) (lambda (s) (display s) (p s)))) "LOVE ")

Of course, the latter two examples rely on unnamed functions (lambdas), which, as it turns out, appear not to be supported at all in Turing. As a result, I could only duplicate the first example:

**(printing “LOVE” an infinite number of times using named recursion in Turing)**

procedure forever(x : string) put x .. forever(x) end forever forever("LOVE ")

Feeling inspired, I decided to try this out in Python. Unfortunately, while lambdas are supported in Python, they are purely functional, meaning it’s impossible to get side effects out of the recursive process like printing “LOVE” every time. You’d have to generate an infinitely long string of these and *then* print it out:

**(printing “LOVE” an infinite number of times using named recursion in Python)**

def FOREVER(x): print x, FOREVER(x) FOREVER("LOVE")

**(the Y combinator in Python)**

(lambda f: \ (lambda x: f(lambda y: (x(x))(y))) \ (lambda x: f(lambda y: (x(x))(y))))

**(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in Python, theoretically)**

(lambda f: \ (lambda x: f(lambda y: (x(x))(y))) \ (lambda x: f(lambda y: (x(x))(y)))) \ (lambda p: (lambda s:(s + p(s)))) \ ('LOVE ')

Of course, you won’t be able to see anything from running that last one. But you can use the Y combinator to print out “LOVE” a finite number of times:

**(printing “LOVE” 17 times using the Y combinator to do anonymous recursion in Python)**

(lambda f: \ (lambda x: f(lambda y: (x(x))(y))) \ (lambda x: f(lambda y: (x(x))(y)))) \ (lambda p: (lambda s: (s==0 and ' ') or ('LOVE ' + p(s-1)))) \ (17)

Feeling even more inspired, I decided to tackle the task of translating this into PostScript, which is totally one of the awesomest programming languages ever, even though many people who are familiar with it don’t realize its programming complexity and dismiss it as a simple page description language … ahem. (It’s the language behind PS files, the precursor to PDF.)

And behold, it worked!

**(printing “LOVE” an infinite number of times using named recursion in PostScript)**

/FOREVER { dup print FOREVER } def (LOVE ) FOREVER

**(the Y combinator in PostScript)**

{ [ exch { [ exch { dup cvx exec exec } aload pop ] cvx } aload pop 8 -1 roll { cvx exec } aload pop ] dup cvx exec }

**(printing “LOVE” an infinite number of times using the Y combinator to do anonymous recursion in PostScript)**

(LOVE ) { [ exch { dup 5 string cvs print [ exch } aload pop 8 -1 roll [ exch cvx { exec } aload pop ] cvx { aload pop ] cvx exec } aload pop ] cvx } cvlit { [ exch { [ exch { dup cvx exec exec } aload pop ] cvx } aload pop 8 -1 roll { cvx exec } aload pop ] dup cvx exec } exec cvx exec

And just for fun, here’s computing the factorial of 6 using the Y combinator:

6 { [ exch { dup 0 eq exch { 1 } exch [ exch } aload pop 9 -1 roll [ exch { dup 1 sub } aload pop 4 -1 roll cvx { exec } aload pop { mul } aload pop ] cvx { aload pop ] cvx ifelse } aload pop ] cvx } cvlit { [ exch { [ exch { dup cvx exec exec } aload pop ] cvx } aload pop 8 -1 roll {cvx exec } aload pop ] dup cvx exec } exec cvx exec

PostScript rocks.

CUZ I DONT DO REVIEWS YO

this is a DIALOGUE on the nature of computation brought to you by °C-ute or actually just THE AIRI AND MAIMI SHOW cuz everybody else is like wut im a computer n00b i dont even know how to type zomgwtf but AIRI AND MAIMI are like SUPER FREAKING GENIUSES or something and they totally know everything about computers and programming and data structures and algorithms and complexity theory and all that

because contrary to popular belief °C-ute is actually short for

**°COMPUTE**

thats right THATS A DASH your supposed to fill in the missing letters duh

(betcha didnt know that huh?)

WUT

oh hay look its °C-ute in the middle of their STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS class and today their going over HIGHER ORDER PROCEDURES and how to call a procedure using another procedure as an argument or even reflexively using the procedure itself

so erika and mai are like WUUUHHHHHH???? but airi and maimi totally know wuts going on cuz their like **SUPER FREAKING GENIUSES** and their already jumping ahead to next weeks topic…..

and airi goes hey check this out zomglolololololol

… one level of embedding …

….. TWO levels of embedding …..

……. FOUR LEVELS OF EMBEDDING ……..

……… **EIGHT LEVELS OF EMBEDDING** IS THAT AMAZING OR WUT OMG???!!! ………

XDDDDDDDDDDDDDDDDDDDDDD

and maimis like WUT

and airis like **RECURSION** B****ES!!!

but maimis like STFU N00B that terminates after only eight iterations

betcha cant do an **infinite loop** wut

so airi sez OH YEAH WELL CHECK THIS OUT

(define (FOREVER x) (display x) (FOREVER x)) (FOREVER "LOVE ")

SEE IT PRINTS OUT **LOVE** AND RECURSIVELY CALLS ITSELF SO IT CAN PRINT OUT **LOVE** AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN AND AGAIN

its like **LOVE** …….. FOREVER!!!!!

**wut**

**FOREVER LOVE**

get it? GET IT??!!!

but maimis like SRSLY zomgrofl **THAT IS SO TRIVIAL IT MAKES THE TRIVIAL GROUP LOOK NONCOMMUTATIVE** lol

NONCOMMUTATIVE?????!!!!!!!

I **OWN** TSUUGAKU VECTOR☂

**I AM THE LIVING EMBODIMENT OF THE INNER PRODUCT OF ANY TWO VECTORS IN A HILBERT SPACE**

cuz thats like **CONJUGATE SYMMETRY**

which when restricted to a real scalar field means that under the inner product any two vectors **COMMUTE**

FOR REAL

oh yeah well thats nothing compared to the **Y COMBINATOR**

(lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))

your procedure is so weak it needs a name zomglol

WITH THE Y COMBINATOR YOU CAN DO **ANONYMOUS RECURSION** ZOMGAWESOME

(((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))) (lambda (p) (lambda (s) (display s) (p s)))) "LOVE ")

LOOK NO NAMES WUT

………………… O__________________O ……………………

THATS RIGHT THE Y COMBINATOR IS SHORT FOR **YAJIMA COMBINATOR!!!!!!**

o rly?

YA RLY **LAMBDA CALCULUS** FTW

well lambda calculus is ok but….

**KAPPA CALCULUS** IS THE BEST!!!!!! =(^w^)=

and maimis like *facepalm*

but then saki butts in and is like

i like **SKI calculus** cuz its like SAKI but like without the A

and airi and maimi are like LOLWUT

**NEXT TIME ON THE AIRI AND MAIMI SHOW FEATURING °C-UTE**

WTFAWESOME **BATTLE OF THE BRAINZ** LIKE ZOMG

**SUPER FREAKING GENIUS** IDOLS DISCUSS COMBINATORY LOGIC AND FORMAL GRAMMARS AND THE CHOMSKY HIERARCHY AND THE COMPUTATIONAL EQUIVALENCE OF RECURSION AND TURING MACHINES!!!!!!

and °C-ute perform **AN INTERPRETIVE DANCE** interpreting THE RUNTIME EXECUTION OF A SCHEME INTERPRETER INTERPRETING ITS OWN SOURCE CODE

LOLWUT kthxbai <33333333 XD

… I’ve just been busy, sorry.

Busy with what, you ask?

Well … I’ve been living it up (?) as a graduate teaching assistant for a course in mathematics for computer science, taken mostly by second-year undergrads, with a total enrollment of around ~180. As part of my duties, I get to teach two sections that meet twice a week and also contribute to writing problems for assignments and quizzes. What fun!

Actually, the making-up-awesome-problems part really is fun! I managed to whip together an entire problem set on the topic of sums and asymptotic relations in which all the problems are Hello! Project-themed.

Alas, after discussion with the other staff members, we decided that while the problems were awesome and hilarious (maybe more so for me than for them), they were a bit on the challenging side, not straightforward enough, and touched on a few topics we weren’t really covering (Problem 4d in particular “would kill the students”). So it got scratched, and a more boring replacement was released instead.

But all is not lost! We’ve decided to release this problem set as optional, not-for-credit “challenge problems”, and you can try them out here:

Hello! Project Challenge Problems (PDF)

If you wish, you can send your solutions to kirarinsnow@mit.edu, and I’ll respond with comments.

Enjoy!

Happy birthday Koharu!

In celebration of Koha’s birthday (07.15), here are a few double dactyls I’ve composed:

**Papancake**

Pancakey pancakey,

Master chef Kirari

Proves she can pancake-sort

Faster than SHIPS.

Quite inexplicably,

This method takes but a

Subpolynomial

Number of flips.

**SUGAO-flavor**

Flavor Flav, baklava,

Koha-chan’s talk of a

“Genuine flavor” is

Just a disguise—

Hard-to-find particle

Actually is quantum

Chromodynamics‘s

Largest in size.

**Hana wo Pu~n**

Kirari pikari,

Koha and Mai, though

Experts at tangent and

Cosine and sine,

Find themselves thwarted by

Trigonometrical

Hippohypoteni:

Transforms affine.

**Konnichi pa**

Konnichi pa-pa-pa!

Kirari’s tra-la-la

Seizes the heartstrings and

Moves one to tears.

Poignantly touched by her

Einführungsmelodie,

Passersby nonetheless

Cover their ears.

More double dactyls are in the works, so stay tuned!

Going over the last few installments of **Pocket Morning Weekly Q&A**, posted in translation at Hello!Online, one might notice a developing interest in mathematics by none other than Michishige Sayumi:

**2008.03.30**

**Question:** *Is there something about which you’ve thought, “Certainly this year, I want to challenge myself with this!”?*

**Michishige:** Math Problems ☆

**2008.05.11**

**Question:** *Fill in the blank to the right with one word. “I’m surprisingly ___”*

**Michishige:** I’m surprisingly intellectual.

Please try to understand that somehow. m(・-・)m

**2008.06.15**

**Question:** *Among your fellow members, what about you makes you think, “At this, I definitely can’t lose!”*

**Michishige:** Simultaneous equations!!

The evidence is indisputable. Sayumi is a math geek. XD

While her fellow MoMusu are busy with more mundane interests, our Sayumi is off challenging herself with math problems (here, Sayu, try Project Euler) and has apparently discovered the wonders of linear algebra (I’m assuming at least some of those simultaneous equations are linear). No doubt Sayumi has mastered the techniques of Gauss-Jordan elimination, Cramer’s rule, and LU decomposition and is well on her way to achieving world domination.

In addition to this, Sayumi has listed Tetris as a hobby and as a “special skill”. This is by far the geekiest interest I’ve seen in any H!P member. Because Tetris is not your average video game. It is a mind-stretching mathematical puzzle, and several of its subproblems are NP-complete. **NP-complete**, I tell you! This places it in the class of difficult problems that includes Boolean *k*-satisfiability, determining the existence of a Hamiltonian path, and Minesweeper.

Sayumi is hardcore.

For this, she gets an **Excellence in Unabashed Geekitude Award**.

And I still need to give Koharu one, don’t I?

Just for fun, and because Goto Maki’s name makes a great programming pun, here’s a function in C/C++ that uses Goto’s name to actually do something (it computes the factorial of a number; the **goto maki** statement makes the program loop over the individual multiplications until the final product is computed):

int factorial(int n) { int p = 1; maki: if (n == 0) { return p; } else { p *= n; n--;goto maki; } }

You can put this in, say, a C++ program like the following:

**gotomaki.cc**

#include <iostream>; using namespace std; int factorial(int); int main() { int n; cout << "Enter a nonnegative integer to factorialize: "; cin >> n; cout << "The factorial of " << n << " is " << factorial(n) << ".\n" << endl; return 0; } int factorial(int n) { int p = 1; maki: if (n == 0) { return p; } else { p *= n; n--; goto maki; } }

and then you too (yes, you!) can factorialize away with Gocchin:

% g++ gotomaki.cc -o gotomaki % ./gotomaki Enter a nonnegative integer to factorialize: 1 The factorial of 1 is 1. % ./gotomaki Enter a nonnegative integer to factorialize: 2 The factorial of 2 is 2. % ./gotomaki Enter a nonnegative integer to factorialize: 3 The factorial of 3 is 6. % ./gotomaki Enter a nonnegative integer to factorialize: 4 The factorial of 4 is 24. % ./gotomaki Enter a nonnegative integer to factorialize: 5 The factorial of 5 is 120. % ./gotomaki Enter a nonnegative integer to factorialize: 6 The factorial of 6 is 720. % ./gotomaki Enter a nonnegative integer to factorialize: 0 The factorial of 0 is 1.

Fun, ne?

Countdown! The Top 100 Hello! Project PVs

My last post has apparently sparked a “laugh riot” of a debate that’s now more than three times as long as my original post. If you haven’t seen it yet, you may find it worth reading. Or maybe not.

As always, I appreciate your feedback, positive or negative. It’s always good to know how effective my communication is.

And now, on to the next batch:

## Recent Comments