Subject: Re: [boost] De Bruijn Bind (alternate bind syntax) Interest?
From: David Sankel (camior_at_[hidden])
Date: 2010-09-02 13:33:18
2010/9/2 Stewart, Robert <Robert.Stewart_at_[hidden]>
> David Sankel wrote:
> > I've been working on an alternate bind syntax based on De
> > Bruijn indices.
> I started to look at the Wikipedia page, but realized there was way too
> much for me to learn to even begin to understand what you mean. Therefore,
> this reference is of no value to anyone without your background.
It requires someone casually familiar with lambda calculus. Lambda
calculus involves the creation of anonymous functions.
Î»v.e declares a new function. v is the identifier bound to the argument and
e is an expression that can use v. For example Î»x.x+1 creates a new function
that returns its argument plus 1. Expressions can include other lambdas
(called abstractions) and function applications.
Consider the function Î»x.Î»y.x+y. This function actually returns another
function which can be applied yet again. Here it is being called with some
((Î»x.Î»y.x+y)(22))(14) â here x is being substituted by 22
(Î»y.22+y)(14) â now y is being substituted by 14.
De Bruijn indices are a way to remove the need for binding a name to the
variable in our function declaration. So, instead of Î»v.e, where e can use
v, we say Î»e where e uses "1" to refer to the argument.
The reason for using 1 is to distinguish between between nested
lambdas. Î»x.Î»y.x(y) becomes Î»Î»2(1). Note that 1 and 2 aren't the normal
arithmetic variants, these are De Bruijn indices. The 2 refers to the outer
lambda and the 1 refers to the inner lambda.
> Here is an example of a function const that takes in an argument c and
> > returns another function that, for all input, returns c:
> > //Î»x.Î»y.x = Î»Î»1 with De Bruijn indices.
> > auto const_ = abs<1>( abs<1>( var<1,0>() ) );
> Presumably, "abs" doesn't mean absolute value as it would in pretty much
> any other programming context. That seems unwise at best.
I disagree. We have namespaces to take care of duplicate identifiers and abs
is the commonly used identifier for lambda abstractions in programming
contexts you might not be aware of.
> More examples, further explanation, and an implementation are
> > available here.
> I found your README. The grammar section assumes I know what you mean by
> "abstraction" and "application," at the least, which I don't. The examples
> section does absolutely nothing for me as I don't understand the syntax or
> terminology. The result is that I can't make anything of your *bind*
Hopefully this helps. Thanks for the feedback.
-- David Sankel Sankel Software www.sankelsoftware.com 585 617 4748 (Office)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk