The Nineteenth Byte

Here's my current programming question, for those Perlites out there. I have two ananymous subroutine references, stored in local variables. I want to create a new anonymous subroutine that runs both of those other subroutine. How do I do it?

Timwi

sub runboth() { my ($first, $second) = @_; $first->(); $second->(); }

Am I missing something?

Oh, anonymous. Er, my $runboth = \{ <the above> }; ?

PhiNotPi

If I change the value of $first later on, would that change the action of the subroutine? I don't want it to.

Wait, that wouldn't be the problem.

Timwi

12:26 AM

Oh, OK. Then you’ll need to wrap it in a closu— oh OK then :)

PhiNotPi

The problem would be that, this runboth() takes the two things to run as arguments.

I want to create a runboth that takes no arguments.

Timwi

my $runboth = \{ $first->(); $second->(); }; ?

Assuming the variables are already called $first and $second.

PhiNotPi

Would changing the values of first and second later on change the action?

Timwi

Yes

OK how did you do the monospace in the end? :)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

VGFicwlmb3IJdGhlCXdpbgkh

Alex A.

12:32 AM

@Timwi ¯\_(ツ)_/¯

(backticks, I just had a misplaced \)

Timwi

Oh OK

Cᴏɴᴏʀ O'Bʀɪᴇɴ

Single or double quotes? :3

PhiNotPi

I'm going to have to do some serious re-working of my lambda system if I can't get this to work.

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@PhiNotPi There's nothing worse than redoing code, IMO

orlp

@PhiNotPi you here?

PhiNotPi

12:38 AM

yes

orlp

considering you asked that question, I have a suspicion you don't know something you want to know

that may or may not amaze you and blow your mind

you understand python, right?

PhiNotPi

Yes

orlp

using lambda functions ONLY, write a recursive function

PhiNotPi

No clue.

Timwi

Y combinator?

orlp

12:39 AM

@Timwi shhh

this is a learning experience

Alex A.

@Timwi I thought that was a venture capital company.

orlp

not a googling experience

Timwi

Hey, I specifically waited until he said “no clue”

Alex A.

@Timwi Why are your quotation marks weird?

Timwi

I did this in C# once, but I don’t remember any of it, so... no hints from me

Uh, “weird”? :) In what way are they “weird”? :)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

12:40 AM

@AlexA. Those quotes are beautiful. “ and ”

orlp

@PhiNotPi let's say I want to do factorial

Timwi

Hah! I did it with factorial too, back then :)

Alex A.

@Timwi They're all... slanty.

@CᴏɴᴏʀO'Bʀɪᴇɴ Incorrect

orlp

def f(n): return 1 if n == 1 else n*f(n-1)

PhiNotPi

sure

Alex A.

12:41 AM

@Timwi Something like this?

orlp

now, obviously this is not using lambda functions, and assigns to a variable f

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@AlexA. ? Why?

Timwi

@AlexA.: Yes, correct quotation marks are usually slanted. That’s completely normal. :)

orlp

but here's the thing

I can write this lambda function:

lambda n, f: 1 if n == 1 else n*f(n-1)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

g'night y'all

orlp

12:43 AM

then, I can write this lambda function lambda f: f(10, f)

@PhiNotPi what would (lambda f: f(10, f))(lambda n, f: 1 if n == 1 else n*f(n-1)) return?

err

Alex A.

A black hole

orlp

one mistake

the first function should be

lambda n, f: 1 if n == 1 else n*f(n-1, f)

and combined function thus becomes

(lambda f: f(10, f))(lambda n, f: 1 if n == 1 else n*f(n-1, f))

@PhiNotPi following it so far?

PhiNotPi

The only thing I've learned is that I know less about lambdas than I thought I did.

orlp

@PhiNotPi the trick here is first-order functions

PhiNotPi

okay, I got it now

orlp

12:50 AM

woops

I couldn't connect to the chat server

PhiNotPi

(My wifi is really bad)

orlp

no its not you

I had the same thing, but could connect to other sites

PhiNotPi

Those two things are not mutually exclusive.

orlp

fair enough

@PhiNotPi ok, so now we have an expression that computes the factorial of 10

PhiNotPi

okay

orlp

12:52 AM

all we have to do now, is make a function out of it

the final part is really easy :)

lambda N: (lambda f: f(N, f))(lambda n, f: 1 if n == 1 else n*f(n-1, f))

PhiNotPi

okay, neat

orlp

and that, is a recursive function, without named functions :)

PhiNotPi

Wow, my program insta-crashes Perl's interpreter.

orlp

@PhiNotPi you can go deeper however

@PhiNotPi in the lambda calculus (on which unnamed functions are based), you can only have one argument for each lambda function

@PhiNotPi so, let's say I want to write a function that multiplies two values

(lambda a, b: a*b)(3, 7)

Timwi

Is this going to be currying?

orlp

12:55 AM

@Timwi shhhh

Timwi

Sorry, I’m just asking

orlp

that works, but uses two variables passed into one function

PhiNotPi

(lambda a: (lambda b: a*b))(3)(7)

?

orlp

~~good!~~

almost

@PhiNotPi try and run it :)

small error

PhiNotPi

It might take a while to install Python.

orlp

12:57 AM

In [67]: (lambda a: (lambda b: a*b))(3, 7)
TypeError: <lambda>() takes 1 positional argument but 2 were given
<lambda>() takes 1 positional argument but 2 were given

PhiNotPi

there?

orlp

that's right :)

@PhiNotPi now apply that same thing to our factorial function:

lambda N: (lambda f: f(N, f))(lambda n, f: 1 if n == 1 else n*f(n-1, f))

Alex A.

@PhiNotPi Python without installation

PhiNotPi

@AlexA. Thanks.

orlp

@PhiNotPi one minor gripe by the way

no need for the inner parenthesis

(lambda a: lambda b: a*b)(3)(7)

PhiNotPi

1:00 AM

In the meantime, I've come up with a really good way to avoid my earlier problem.

orlp

@PhiNotPi is it working?

making everything into single arguments?

PhiNotPi

How do I get that lambda to run on the site Alex mentioned?

Alex A.

Copy and paste into the REPL

orlp

repl.it/BGoa

or that

PhiNotPi

okay, I just had some parenthesis not copy-pasted

No, I don't know how to curry it.

orlp

1:09 AM

@PhiNotPi done?

oh ok

ok, I'll repeat the same thing here:

lambda N: (lambda f: f(N, f))(lambda n, f: 1 if n == 1 else n*f(n-1, f))

there's two places where we're calling f: on the left and on the right

so f(N, f) should become f(N)(f)

then, we must change lambda n, f: to lambda n: lambda f:

Alex A.

^ This is how you curry it

orlp

@PhiNotPi does that help?

PhiNotPi

lambda N: (lambda f: f(N)(f))(lambda n: lambda f: 1 if n == 1 else n*f(n-1)(f))

orlp

leave off the print

that's just for debugging

same for the call

good!

@PhiNotPi there is a little nugget of beauty and simplicity that's still being hidden here, however

@PhiNotPi swap the order of the N and f arguments

(in a new line, not edited)

PhiNotPi

lambda N: (lambda f: f(f)(N))(lambda f: lambda n: 1 if n == 1 else n*f(f)(n-1)) ?

orlp

1:18 AM

correct

now, let's say you were golfing

and let's ignore the last part of the lambda

is there a shorter way to write this?

lambda N: lambda f: f(f)(N)

to make it easier, let's change the middle part too

PhiNotPi

Not sure, but the f(f) feels highly redundant.

orlp

lambda N: BLA(N)

is there a shorter way to write that?

@PhiNotPi remember, BLA is a function

maybe I need to make it a bit less abstract

PhiNotPi

Just leave off the lambda N, so BLA(N) ?

orlp

@PhiNotPi almost

lambda N: BLA(N) is an expression that's a function

BLA(N) is a value that you get from calling BLA

@PhiNotPi can you simplify this? print((lambda N: math.factorial(N))(10))

PhiNotPi

Other than the print(math.factorial(10)) not sure.

orlp

1:26 AM

exactly!

(lambda N: math.factorial(N)) simply is math.factorial

remember, functions are values too!

Timwi

(note math.factorial, not math.factorial(N))

orlp

math.factorial is a function

Alex A.

What is N.B.?

No brainer?

orlp

math.factorial(N) is a number that is the factorial of N

Alex A.

Not Butter?

orlp

1:27 AM

@AlexA. nota bene

Alex A.

Not a Bean?

Timwi

Nota bene. Please excuse my Latin. :-p

Alex A.

What's it mean?

Timwi

“Not a Bean” is shockingly close :-D

It means “please note”.

orlp

@PhiNotPi so, what is lambda N: BLA(N)?

PhiNotPi

1:28 AM

BLA

orlp

correct

so, what is lambda N: lambda f: f(f)(N)?

PhiNotPi

lambda f: f(f)

orlp

yes!

so, can you now simplify this?

lambda N: (lambda f: f(f)(N))(lambda f: lambda n: 1 if n == 1 else n*f(f)(n-1))

PhiNotPi

Could you just leave off the whole first part?

orlp

not quite

Timwi

1:31 AM

Think about exactly which parts of (lambda N: math.factorial(N))(10) you removed and which stayed

PhiNotPi

well, I'm not sure what to make of (lambda f: f(f))(lambda f: lambda n: 1 if n == 1 else n*f(f)(n-1))

orlp

but that's it!

@PhiNotPi if f(f)(N) is the factorial of N, then that makes f(f)...?

PhiNotPi

I would assume the factorial function.

orlp

correct

do you understand it now?

that whole expression above is the factorial function

(lambda f: f(f))(lambda f: lambda n: 1 if n == 1 else n*f(f)(n-1))(10) would be the factorial of 10

Alex A.

How not to golf in Python

Timwi

1:35 AM

# You can put it in a variable :)
factorial = (lambda f: f(f))(lambda f: lambda n: 1 if n == 1 else n*f(f)(n-1))
factorial_of_10 = factorial(10)

OK not sure why the backticks don’t work now

orlp

@Timwi press the 'fixed font' button to the right of send/upload

it's for
multiline messages

PhiNotPi

Backticks don't work on multi-lined chat messages.

Alex A.

@Timwi Inline formatting doesn't work in multiline messages

Oof, ninja'd

Timwi

Apparently nor does the “fixed font” thing. It only works if you want to fix-font the whole message...

orlp

@Timwi ah yes

@PhiNotPi but now we can see a pattern

Timwi

1:38 AM

Kinda weird. Why wouldn’t they have it support Markdown? We are on StackExchange, after all

Alex A.

@Timwi Chat supports a subset of markdown. Enough to make ~~users~~ everyone but Timwi happy but not enough to make the devs want to kill everything.

orlp

(lambda f: f(f))(lambda f: ___________________)

Timwi

@AlexA.: I’m not happy ;-)

(and I’m a user, if it wasn’t clear :) )

Alex A.

Better?

orlp

@PhiNotPi whatever is in the expression ___________, it can be a recursive function by simply calling f(f) instead of f

Timwi

1:40 AM

lambda f: f(f))(lambda f: f(f))     # StackOverflow

orlp

@Timwi nope

Timwi

Yeah, no :)

(lambda f: f(f))(lambda f: f(f)())     # StackOverflow now? :)

orlp

actually

hrm, your first version was stack overflow

Sp3000

The first one is unmatched ) parens :P

orlp

yeah, but after fixing that

actually, no, yeah, that was a perfectly fine SO

I got thrown off

Timwi

1:43 AM

I’m off to bed, I should have left hours ago

orlp

(lambda f: f(f))(lambda f: f(f)) is the same as def f(): f()

Timwi

You guys are too interesting

Then how would you express def f(): f ?

Alex A.

@Timwi NOT ME! :D

My job is to ~~troll~~ moderate.

Timwi

Well right now, I’m a little more than just “moderately” entertained

orlp

(lambda f: f)(lambda f: f)

Timwi

1:45 AM

You cheated, you changed the first part

That’s just the same as lambda f: f

Alex A.

Are You Not Entertained?

►

orlp

@Timwi the problem here is that you have made a 0 argument function, which doesn't exist in lambda calculus

(lambda f: f(f))(lambda f: lambda: None)

Timwi

Ooooh good point

orlp

@Timwi on top of that def f(): f returns nothing :)

Timwi

OK really off now

Well I don’t know the details of Python semantics, but you know what I mean by def f(): f

orlp

1:48 AM

@PhiNotPi as an excercise, using the pattern (lambda f: f(f))(lambda f: ___________________), can you now write a function that takes a list of integers, and returns their sum?

@Timwi def f(): return f

Timwi

Then surely you should have written def f(): return f() in chat.stackexchange.com/transcript/message/23995847#23995847, even if it makes no difference to the stack overflow :)

orlp

@Timwi yeah my bad

Timwi

Please turn off this chat, otherwise I won’t be able to go to bed

orlp

@PhiNotPi (and using only l[0] and l[1:] to index)

Timwi

Right now I’m too tempted to actually write that integer sum function (but in C#)

orlp

1:51 AM

@Timwi what?

you're not done yet? :P

Timwi

I am in my head...

I’m resisting the urge of going any further than that

Alex A.

@Timwi I can freeze the chat room but I think my fellow mods would be pissed

As well as everyone else

Timwi

Sigh. Then I guess I’ll have to stay up the whole night

I mean the remaining half of the night

Alex A.

Do it.

Timwi

I have to be somewhere in 11 hours!

Alex A.

1:52 AM

Irrelevant.

orlp

@Timwi make it come to you!

Timwi

I can’t, I don’t have a piano.

orlp

def appointment(there): return here

Timwi

Byebye.

zzzzzzzzzzzzzz

Alex A.

Spend the next 11 hours manufacturing a piano out of things in your house.

(that actually sounds pretty fun)

Sp3000

2:02 AM

"Hey Honey, why's there a hole in the wall?" "Sorry love, had to borrow some wood for the piano project"

Alex A.

Haha exactly! :D

orlp

@PhiNotPi seems like you have died and/or are gone, either way, what I just explained to you (in googlable terms) is the Y combinator, currying, and part of the lambda calculus

PhiNotPi

okay

orlp

the beauty of it is that since you can write recursion using single-argument lambdas, you've shown that single-argument lambdas are turing complete :)

PhiNotPi

I'm working on vector calc homework, and some other stuff

Alex A.

2:14 AM

I showed you a picture of panang curry

That's all you need

orlp

@ChrisJester-Young I have a fun fact

if, or cond, or whatever your conditional evaluation might look like in your language is not necessarily a primitive (or in lisp, a special form), and can be derived from other constructs

Chris Jester-Young

@orlp Well, at the base of it, one of if, cond, or and is required.

orlp

@ChrisJester-Young wrong

Chris Jester-Young

Or, hash table with boolean as key, lambdas as values.

orlp

(defun true (then else) then)
(defun false (then else) else)

Chris Jester-Young

2:21 AM

No, in Scheme that is not valid.

Booleans are supposed to be disjoint from procedures.

in the same way that Church numerals are not a valid implementation of numbers in a standard-compliant Scheme.

orlp

@ChrisJester-Young that's a choice though, I never said scheme specifically

Chris Jester-Young

Fine, but you know me, I think about everything from a Scheme perspective.

orlp

@ChrisJester-Young a simple indexed array as primitive would be enough too

Chris Jester-Young

How would you convert a boolean into an index?

without using if, that is.

You'd still need a hash table.

Then you may as well make a boolean->procedure hash table.

orlp

@ChrisJester-Young I was thinking 0 = false 1 = true

in general, all you need is any mapping from two distinct values you call true and false using primitives to two procedures

Chris Jester-Young

2:25 AM

Well, because of disjointness of types (again with Scheme), booleans aren't implicitly convertible to fixnums.

orlp

for example, in Python [lambda a, b: b, lambda a, b: a][True]

since True == 1

Chris Jester-Young

Again, I'm still thinking from a Scheme perspective.

orlp

@ChrisJester-Young I'm talking on a more fundamental level than scheme

Chris Jester-Young

Right.

orlp

the idea that conditional evaluation is not necessarily an axiom is a powerful idea

Mauris

2:27 AM

I have more short cat implementations left, dangit.

orlp

you might choose other axioms that are mutually exclusive with a non-axiomatic conditional

but that doesn't change the fact that there are legitimate systems in which if does not have to be axiomatic

Chris Jester-Young

I'm happy to do non-axiomatic conditionals; like I said, you can use a hashtable lookup in Scheme.

Anyway, it's an interesting implementation idea.

Maybe I'll toy with it a little.

(I've been meaning to write an R7RS implementation in C++11 for a while.)

orlp

@ChrisJester-Young even without the hash table lookup

the beauty of it

is that simply by saying

(defun true (then else) then)
(defun false (then else) else)

I can now implement algorithms expressed using conditionals, without ever using a special form for it

undergroundmonorail

@BetaDecay i did it. i wrote your cake program

orlp

that might not correspond to the true/false that the language has chosen to be 'official', but that's irrelevant

undergroundmonorail

2:31 AM

but at what cost

orlp

@undergroundmonorail since this is programming golf, I presume minimal cost

undergroundmonorail

great cost to my own sanity, and also i might have summoned a lovecraftian horror by mistake

Chris Jester-Young

@undergroundmonorail Codethulhu?

@orlp Sure, that's like "Church booleans" (to extrapolate from Church numerals).

undergroundmonorail

it's probably not a good sign for the language i designed if i, the person who understands it the best in the world almost certainly, write programs in it and then throw my hands in the air saying "it works and i don't know how but i'm done touching it"

orlp

@ChrisJester-Young exactly, that was the fun fact :P

Chris Jester-Young

2:35 AM

:-D

orlp

@ChrisJester-Young I've been implementing my own scheme too

mostly done with garbage collection

Chris Jester-Young

@orlp Apparently, Church boolean is a real term.

Church encoding

In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The data and operators form a mathematical structure which is embedded in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded data in the lambda calculus this way. Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to higher-order functions under Church encoding. The Church-Turing thesis asserts that...

orlp

IIRC there was something I fundamentally disagreed with with the official scheme spec

but I can't remember :(

Chris Jester-Young

@orlp Too bad, because I'd be curious to hear.

orlp

@ChrisJester-Young well, here we go again... trac.sacrideo.us/wg/raw-attachment/wiki/WikiStart/r7rs.pdf

Chris Jester-Young

2:39 AM

@orlp GC, hygienic macros, and continuations are probably the 3 hardest things to implement in a Scheme implementation.

orlp

@ChrisJester-Young I wasn't entirely done yet, but I think I had nailed GC

obviously not the most optimized insane thing, but it was a compacting moving stop-the-world GC

Chris Jester-Young

Nice (or at least nicer than conservative GCs), but I'm fascinated by the parallel GCs that the JVM has....

orlp

@ChrisJester-Young I fundamentally disagree with the JVM =/

if people shipped something the equivalent of LLVM IIR, you could do the same thing, native

Chris Jester-Young

@orlp Do you disagree with JVM because it's a managed execution environment? Or something else?

orlp

@ChrisJester-Young I disagree with virtualizing the CPU

Chris Jester-Young

2:43 AM

@orlp It doesn't virtualise the CPU though. It runs natively, with the aid of a JIT compiler.

PhiNotPi

If I get lambdas to work in my language as I think they will, it will be most terrific.

orlp

@ChrisJester-Young that's an optimization of the virtualization :)

PhiNotPi

"terrific" defined as "terror-inducing"

Chris Jester-Young

@orlp In the 90s, you could think that way. But in this millennium, I don't think anybody thinks of the JVM as an interpretation-based system.

orlp

lambda l,o,v,e,c,r,a,f,t:'he comes'

Chris Jester-Young

2:45 AM

12 mins ago, by Chris Jester-Young

@undergroundmonorail Codethulhu?

orlp

@ChrisJester-Young the thing is, JIT has its place, but not when ahead-of-time could do the exact same thing

I wouldn't mind JIT'ing stuff to get faster workflows while in development

(just like running with -O0)

Chris Jester-Young

See, the only downside of JIT is the warmup cost. But there are some optimisations that are JIT-only and cannot be done by AOT.

Profile-guided optimisation, for example.

orlp

@ChrisJester-Young that's not true

you can do profile-guided opt AOT

Chris Jester-Young

Can it dynamically adapt the optimisation strategy based on the current workload?

Because, the JVM in Java 6+ does that.

orlp

@ChrisJester-Young no, but I'd argue such workloads are exceedingly rare, and if they exist you can detect and program for them

Chris Jester-Young

2:50 AM

Why should the programmer be burdened with programming for them, though?

when the runtime can Do The Right Thing for you?

orlp

@ChrisJester-Young because the runtime can't do that

the runtime Can Randomly Make Your Program Slower In The Hope It Stumbles Upon An Optimization

Chris Jester-Young

So the runtime keeps statistics and optimises for the "happy path" (the common case, as detected by statistics).

orlp

@ChrisJester-Young detection is very expensive

Chris Jester-Young

There's still a deoptimised version for unhappy paths.

orlp

so is statistics

and so is optimization

if possible, you want to load it to compile time

Chris Jester-Young

2:52 AM

I would say that the costs of such things are amortised by the performance gains you get.

Maybe I have drunk the John Rose Kool-Aid, but I'm a huge believer of JIT.

orlp

@ChrisJester-Young clearly they're not, otherwise Java should beat C / C++ on a more regular basis than carefully constructed examples

Chris Jester-Young

In related news, I want to try to make a Scheme implementation that is as performant as C++, but I know that's a long shot.

orlp

@ChrisJester-Young I believe JIT can be a viable strategy in some niche cases (like really extreme workloads with lots of 'happy paths'), but I believe the default should be AOT, with JIT available on request by the user

Chris Jester-Young

Certainly, the .NET designers agree with you, because every time you install a new assembly, ngen gets run....

Transcript for