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
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.

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:

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!

(see Part 2)

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 ;
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; } } [/sourcecode] 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:

### Remixes

DJ Kirarin☆Snow ☃'s remixes are now appearing at K!☆Mixed.