< User:Chibi-Matoran‎ | Wiki

During your time on Scratch, you may have come across the word "lambda." Perhaps people were discussing it on the forums. Perhaps a Scratcher asked if they would be added to Scratch. Now, you're scratching your head and asking to yourself, "What is a lambda?"

Simply put, a lambda is a first-class function. What is a function, and how can it be "first-class?" This definition requires a deeper explanation.

What's a function?

Let's start with functions. If you've programmed in another language, you are probably already familiar with them. In Scratch, a function is a block. It may take some inputs ("arguments") or return a value. An example of a function is the add block. It takes two numbers as inputs, and returns their sum.

((4) + (3)) //Returns 7

Functions must have definitions. In Scratch, the definitions of built-in blocks are programmed in the interpreter, but programmers may also create their own custom blocks. Functions are defined by scripts.

define addOne (num)
say ((num) + (1)) for (2) secs
say [Yay!] for (2) secs

This function takes a number as an argument, adds one to it, and tells the sprite to say the sum for two seconds. Then, it tells the sprite to say, "Yay!" for two seconds. After defining this block, Scratchers can use it in their scripts to make the sprite say the result of adding one to a number of their choice, then say, "Yay!"

when gf clicked
addOne(3)::custom
addOne(7)::custom

When a custom block is run, the variables specified in the define hat block are given the values in the block inputs. Then, the blocks under the define block are executed. The above script makes the sprite say, "4" for two seconds, say, "Yay!" for two seconds, say 8 for two seconds, then say, "Yay!" again for two seconds.

What's first-class?

Even though you don't know what first-class is, it's all around you, and allow you to do the most basic of computations conveniently.

A first-class citizen is a citizen which can be operated on using all the standard operations of a programming languages. These usually include:

  • Being passed to a function
  • Being returned from a function
  • Existing without an identifier (exist without being the value of a variable)
  • Being assigned to a variable

What do these requirements mean?

Being passed to a function

say [Hello, world!]

Strings are first-class in Scratch. Here, the string "Hello, world!" is an input to a block.

Being returned from a function

((2) + (3))

Numbers are first-class in Scratch. Here, a block is returning the number 5. This example also demonstrates the requirement of passing to functions; the numbers 2 and 3 are being passed to the block.

Existing without an identifier

((2) + (3))

Huh, isn't this the same example from last time? Yes, it is! This script shows numbers existing without an identifier. Such a feature may sound complicated, but you take it for granted without even realizing it. In Scratch, you can just type the number that you want to use.

A fancier term for this is "anonymous." The numbers 2 and 3 are anonymous because they being used without being held in a variable. Values written this way are called "literals."

Being assigned to a variable

set [foo v] to [abc]

This example shows the variable "foo" being set to the string "abc."

So, what are lambdas?

Now, we know what functions are and what first-class is. A first-class function is a function that can:

  • be passed to another function
  • be returned from a function
  • exist as a literal
  • be set to a variable

Scratch's way of declaring functions involves giving them names, and having a new block show up in the palette. This way of implementing functions does not enable anonymous functions to be used. In Snap!, a Scratch modification, a "ring" block is used for a function literal. We will be using it for our examples. We will also be using Snap!'s blocks for calling lambdas.

({say ((num) + (1)) for (2) secs
say [Yay!] for (2) secs} input names: (num)::ring grey)

This is the same custom block from out first example, but in the function literal notation. We can set it to a variable:

set [addOne v] to ({say ((num) + (1)) for (2) secs
say [Yay!] for (2) secs} input names: (num)::ring grey)

Then, we can call it:

run (addOne) with inputs (3)::control
run (addOne) with inputs (7)::control

The "run" block takes a function and zero or more arguments as its inputs, then sets the variables specified in "input names" of the function to the arguments listed. Then, the script inside the ring is executed. The above script is equivalent to running the custom block twice, with 3 and 7 given as its arguments for each call, respectively.

Note Note: In Snap!, the "Run" block is used for lambdas which don't return values (stack blocks) while the "Call" block is used for lambdas which do (reporter blocks).

Because lambdas are first-class, we can pass them to other functions, or return them from functions. Functions that accept or return other functions are called "higher order functions."

set [while v] to ({repeat until <not(call (condition)::control)> 
run (body)::control
end}input names: (condition) (body) ::ring grey)

The block "while" acts as a while-loop, the opposite of Scratch's repeat-until loop. It accepts two functions as inputs: The conditional expression to be evaluated, and the body of the loop. The block repeatedly runs the condition variable, then the body variable, until the former variable evaluates to false.

Closures

Using the "closure" feature, lambdas can be used to maintain state. State is the current value of all the variables at a given point in time.

define closure demo
set [n v] to (1)
return({set [n v] to ((n) * (2))
return (n)::control cap}::ring grey)::control cap

The "closure demo" custom block returns a lambda that doubles the value of the variable n. Notice that though n is initialized to 1 in the outer function, the returned function does not have any code for initializing the variable before using it. What will happen when we run it?

Note Note: This example uses custom reporters, which Scratch does not support.

set [state maintainer v] to (closure demo::custom)
repeat (3)
    say (call (state maintainer)::control) for (2) secs
end

The variable "state maintainer" is initialized to the function returned by the "closure demo" function. Then, the function held in the variable "state maintainer" is executed three times.

At the start, the value of n is 1. When the lambda "state maintainer" is called, n is doubled, then said for two seconds. The variable n is now 2. When the function is executed for a second time, the value of n starts at 2. It is doubled, then the new value, 4, is said. On the last iteration of the loop, n starts as 4, is doubled, then its updated value, 8, is said for two seconds.

How do closures work?

When a function is run, a new frame is also created. A frame is essentially a set of bindings.

When you use this lambda:

({script variables (a) (b) @delInput@addInput::grey
set [a v] to [0]
set [b v] to [Hello World!]}input names: (x) @delInput@addInput::ring grey)

you are creating this frame:
____
a: 0
b: "Hello World!"
x: ???
____

The frame in which the new frame is created is its parent. A frame can access the bindings in its parent and further frame down the line.

set [myLambda v] to ({script variables (a) (y) @delInput@addInput::grey
set [a v] to ({
script variables (a) (x) @delInput@addInput::grey
set [a v] to [Hello World!]
set [x v] to [7]
say (a) for (2) secs}@delInput@addInput::ring grey)
set [y v] to [42]
report (a)::control cap}input names: (x) @delInput@addInput::ring grey)

This code consists of a lambda within another lambda. The outer lambda has a variable called a that is set to the inner lambda. The outer lambda returns a.

The code results in this environment:
____
myLambda: (the outer lambda)
____

 ^
/_\
 |  Parent
 |

Outer lambda's frame:
____
a: (the inner lambda)
y: 42
____

 ^
/_\
 |  Parent
 |

Inner lambda's frame:
____
a: "Hello World!"
x: 7
____
The bindings in a frame closer to the current frame and farther from the global environment take precedence over the bindings in a frame closer to the global environment. Therefore, this code:

set [myInnerLambda v] to (call (myLambda)::control)
run (myInnerLambda)::control

causes the sprite to say, "Hello World!"

First, myLambda is called. It sets the a in its environment to the inner lambda, then returns it. MyInnerLambda is set to that inner lambda.

Then, myInnerLambda is ran. According to the inner lambda's definition, a variable called a is set to "Hello World!", x is set to 7, then the value of a is said for 2 seconds. The a in the inner lambda's frame is set to "Hello World!", then it is said.

However, what if the inner lambda didn't have a variable called a?

set [myLambda v] to ({script variables (a) (y) @delInput@addInput::grey
set [a v] to ({
script variables (x) @delInput@addInput::grey
set [x v] to [7]
//[The inner lambda doesn't define a variable called "a."]::grey
//[What will the sprite say?]::grey
say (a) for (2) secs}@delInput@addInput::ring grey)
set [y v] to [42]
report (a)::control cap}input names: (x) @delInput@addInput::ring grey)

Instead, myInnerLambda uses the a in its parent frame, the frame created by the outer lambda. The outer lambda's a is set to the inner function, so the sprite says the inner function (a picture of it appears in the speech bubble). Crazy!

Object-oriented programming

Using closures, we can implement object-oriented programming.

Object-oriented programming is a programming paradigm involving the collection encapsulation of values under data structures called "objects," and message passing between such objects. In simple words, an object is a value which is made up of other values, and which can be operated on. We will be demonstrating object-oriented programming with lambdas and closures.

define Point Constructor
set [x v] to (0)
set [y v] to (0)
return ({
if <(message) = [x]> then
return (x)::control cap
end
if <(message) = [y]> then
return (y)::control cap
end
if <(message) = [setX]> then
return ({
set [x v] to (val)
} input names: (val)::ring grey)::control cap
end
if <(message) = [setY]> then
return ({
set [y v] to (val)
} input names: (val)::ring grey)::control cap
end
} input names: (message)::grey ring)::control cap

The above is a "constructor," a function which returns a new object. This script is a bit complicated, so let me walk you through it.

set [x v] to (0)
set [y v] to (0)

This part of the script initializes x and y to 0. These two variables are part of the object's state, and are what we use the closure feature to modify. When a variable is set to a Point object, it maintains their values.

return ({
if <(message) = [x]> then
return (...)::control cap
end
if <(message) = [y]> then
return (...)::control cap
end
if <(message) = [setX]> then
return (...)::control cap
end
if <(message) = [setY]> then
return (...)::control cap
end
} input names: (message)::grey ring)::control cap

This portion of the custom block is the object that is returned. As you can see, the "object" that we are talking about is in fact another function. It consists of a "message" parameter and if-then branches, which return different values based on the message. The messages are the object's keys, and the returned objects are their corresponding values.

if <(message) = [x]> then
return (x)::control cap
end
if <(message) = [y]> then
return (y)::control cap
end

The first two message responses are simple enough. If the message is x, the value of the x variable is returned. If the message is y, the variable of the y variable is returned.

if <(message) = [setX]> then
return ({
set [x v] to (val)
} input names: (val)::ring grey)::control cap
end
if <(message) = [setY]> then
return ({
set [y v] to (val)
} input names: (val)::ring grey)::control cap
end

The values for the keys "setX" and "setY" are functions for changing the values of x and y, respectively. Both of the functions accept a value, the new variable value.

Let's see the object in action.

set [point instance v] to (Point Constructor::custom)

This script sets the variable "point instance" to a new Point object returned from the "Point Constructor" function. Remember, this object is a lambda. The variables x and y, whose values exist in the returned object function, are currently both 0.

Now, let's get the value of x, and say it.

say (call (point instance) with inputs [x]::control) for (2) secs

This script calls "point instance" with the input "x" (Remember that the "point instance" object is a function). If we check the if-then branches of the object returned from the Point constructor function, then we can see that if the message is "x," then the value of x is returned. The value 0 is said for two seconds.

Then, let's mutate x.

run (call (point instance) with inputs [setX]::control) with inputs [10]::control

Don't let the double function call scare you; this script is very simple. First, the "setX" message is passed to the "point instance" object. The object returns a lambda containing code for setting x to an input. This lambda is called in the "run" block, with the input 10. As a result, x is now 10.

Let's check the value of x:

say (call (point instance) with inputs [x]::control) for (2) secs

The value changed!

A little background information about lambdas

First-class functions originated from lambda calculus, a branch of computer science invented by Alonzo Church in the 1930s. Lambda calculus deals with special functions, and gives us many of the principals that we see in first-class functions today.

Lambdas are also closely related to functional programming, a programming paradigm avoiding side effects, and emphasizing "pure" functions which are guaranteed to always give the same output for a given input.

Please let me know if this tutorial contains any errors.