Functions on the left side of an assignment

GoRace Experiment

GoRace es una aplicación web diseñada por gente de la Universidad de Cádiz (opens in a new tab) para gamificar un conjunto de actividades. Visita la página de aterrizaje en https://gorace.uca.es/ (opens in a new tab). Una vez que el director de carrera/profesor ha fijado la carrera, el progreso del corredor/estudiantes en las actividades se visualiza como una carrera olímpica fijada por el director.

Como TFM, nuestro estudiante Claudio Nestor (opens in a new tab) está escribiendo una aplicación web de extensión (un servicio web más un Cli, más una aplicación GitHub) para GoRace que permite alimentar una "carrera" de GoRace con los resultados de los estudiantes proporcionados por el sistema de calificación automática de GitHub Classroom.

El software ahora está alcanzando un estado en el que podemos realizar una prueba de preparación (opens in a new tab) y, por lo tanto, tenemos la intención de usarlo para el laboratorio left side.

Muchas cosas pueden salir mal con este experimento. Solicitamos su comprensión ante los errores y dificultades que seguramente surgirán.

Actualmente, el sistema no está preparado para detectar trampas. Como siempre, contamos con tu compromiso para cumplir las reglas y jugar limpio.

Si quieres colaborar con nosotros, sigue estas instrucciones

Antes de comenzar la carrera rellene este cuestionario (opens in a new tab).
Este cuestionario es tanto para conocer su información demográfica y también tiene que contestar el [test de Bartle]¹ para determinar su perfil de jugador (Pre-Cuestionario). Este cuestionario debería realizarse el primer dia de la experiencia, a ser posible antes de comenzar con la carrera
You will receive an email to register for the race. Please click on the link to accept your registration in GoRace.
Cuando les llegue el email de registro recuerda que tienes que elegir un Nickname y un Password para finalizar el registro y como consejo, recuerda que el Nickname no es el correo electrónico, sino el nombre que tendrá su avatar en la carrera (pasa a veces que los alumnos ponen el correo o el identificador de la universidad).
Do not start pushing to the assignment repo until you have filled the cuestionario (opens in a new tab) and accepted the race.
La carrera se abrirá el viernes 05/04/2024. Hay dos carreras a la vez, una de prueba GITHUB_TEST y la otra reaL PLULL24. Asegúrate de que estás en la carrera correcta (PLULL24).

The Bartle Test is a test based on the player types identified by Richard Bartle in his paper, Hearts, Clubs, Diamonds, Spades: Players Who Suit MUDs (opens in a new tab). Read this paper if you wish to find out more about your player type, and what it all means. Bartle revisits and expands upon these ideas in his book, Designing Virtual Worlds, which is also recommended if you wish to delve a little deeper. ↩

Goal: Functions on the left side of an assignment

Watch the video of Monday 2024/03/18 that day up to minute 35 to understand the motivation for this lab and some incoming labs.

The summary of the idea being that although you can do assignment to elements of an array or a property of an object in most programming languages:

> a = [4,3,1]
[ 4, 3, 1 ]
> a[1] = 8
8

But, as far as I know, direct function value assignment is not a feature we can found in conventional programming languages:

> f = x => x +1
[Function: f]
> f(2) = 9
Uncaught ReferenceError: Invalid left-hand side in assignment

That is, you can't do an assignment to an element of a function. If you stop to think about it, both arrays and objects can be thought as functions.

The array [4,3,1] can be thought as a function that maps 0 to 4, 1 to 3 and 2 to 1.
The object {a: 4, b: 3, c: 1} can be thought as a function that maps a to 4, b to 3 and c to 1.

We want to invent a language in which you can change the behavior of a function via assignments, in the same way you can change the value of an element of an array or a property of an object.

f = fun(x) { x +1 },
f(2) = 9 
write(f(2)), # 9
write(f(3))  # 4

At this time, in our calculator language, the left side of an assignment only an ID is allowed. We want to extend the language to allow the modification of functions.

Introduction

We want to extend the language so that on the left side of an assignment you can have a function modification. For example, the following code should be valid:

test/data/input/fun.calc

f = fun(x) { x + 1 },
f(0+2) = 8, 
f(1+3) = 1000,
write(f(0)), # 1
write(f(2)), # 8
write(f(4))  # 1000

The translation of the former code can be s.t. like the following:

test/data/expectedjs/fun.js

➜  left-side-solution git:(main) bin/calc2js.mjs test/data/input/fun.calc      
#!/usr/bin/env node --stack-size=65500
const { functionObject, Complex, assign, write } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $f;
 
((((
$f = functionObject(function($x) { return $x.add(Complex("1")); }), 
assign($f, [Complex("0").add(Complex("2"))], Complex("8"))), 
assign($f, [Complex("1").add(Complex("3"))], Complex("1000"))), 
write($f(Complex("0")))),
write($f(Complex("2")))),
write($f(Complex("4")));

When you run the former code you get the following output:

➜  functions-solution git:(array-map) bin/calc2js.mjs test/data/input/fun.calc | node
1
8
1000

Scope Analysis revisited

🚫

Let us consider the consequences of the propposed modification on the left side from the perspective of scope analysis.

Notice that

a = fun (x) { x + 1 }
a(3) = 4

Line 1 is a declaration/definition but line 2 is an assignment.

When we do our translation a(3) = 4 becomes:

assign($f, [Complex("3")], Complex("4"), 0)),

Therefore, during scope analysis we have to take into accoun that this kind of assignment is not a declaration/definition of a new entity but a modification.

Modifying a function with nested calls on the left side

Let's consider the following example in which a nested call occurs in the left hand side of the assignment:

test/data/input/fun-on-the-left-side.calc

➜  functions-solution git:(left-side) cat test/data/input/fun-on-the-left-side.calc            
f = fun(x) { fun(y) { x + y } },
f(2)(3) = 8, 
write(f(2)(3)),  # 8
write(f(2)(5)),  # 7
write(f(3)(1)),  # 4
write(f(9)(2))   # 11

The former code modifies the code of the function $f created in the first assignment

test/data/expectedjs/fun-on-the-left-side.js

➜  left-side-solution git:(main) ✗ cat  test/data/expectedjs/fun-on-the-left-side.js
#!/usr/bin/env node --stack-size=65500
const { functionObject, assign, Complex, write } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $f;
 
((((
$f = functionObject(function($x) { 
    return functionObject(function($y) { 
        return $x.add($y); 
    });
}), 
assign($f, [Complex("2"), Complex("3")], Complex("8"))), 
write($f(Complex("2"))(Complex("3")))), 
write($f(Complex("2"))(Complex("5")))), 
write($f(Complex("3"))(Complex("1")))), 
write($f(Complex("9"))(Complex("2")));

Nested calls on the left side and a function on the right side

In this example the assignment on line 6 modifies the function f so that f(1) returns a function that squares its argument:

f = fun(x) { 
      fun(y) { 
        fun (z) { x + y + z }
    }
},
f(1) = fun(y) { y*y },
print(f(1)(3)),   #  9
print(f(2)(3)(5)) # 10

Is for that reason that f(1)(3) is the square of 3 and f(2)(3)(5) is 2 + 3 + 5 that is 10.

Empty arguments on the left side

We are going to consider that when a call to a function occurs on a left side of an assignment expression it has to have argument.

f = fun() { 1 },
f() = 8 # Error message

Somehow the reason for such design is for analogy to what most programming languages do for arrays and objects. For example, in JavaScript you can't do s.t. like a[] = 8. You have to mention an index or a key.

When you run the former code you get the following output:

➜  functions-solution git:(array-map) bin/calc2js.mjs test/data/input/fun-empty-on-the-left-side.calc  
Error: Can't assign to "f" with no arguments

Types and symmetry

The new feature should work with all the types supported by the calculator language. Here is an example for booleans:

test/data/input/fun-on-the-left-side-boolean.calc

f = fun(x) { fun(y) { x + y } },
f(true)(3) = 8,    # 
write(f(true)(3)), #  8 true has an equals method!
write(f(true;4)),  # 5
write(f(4)(true))  # 5

The notation f(true;4) is equivalent to f(true)(4) and will be introduced in the section Currying and multiple arguments for functions of this lab.

For strings:

test/data/input/fun-on-the-left-side-string.calc

f = fun(x) { fun(y) { x + y } },
f("string")(3) = 8,
f(2)("string") = 9,
write(f("string")(3)), #  8 
write(f("string")(4)), # "string4"
write(f(2)("string")) # 9

When the argument/index is a function:

test/data/input/fun-on-the-left-side-function.calc

f = fun(x) { fun(y) { x + y } },
g = fun(y) { y*y },
f(g) = fun(v) { f(g(v))(3) },
write(f(2)(3)), #  5 
write(f(g)(4))  # 19

Consequences: Object Oriented Programming

Notice that the new feature is quite powerful. Object oriented programming can be done with it. For example

test/data/input/object.calc

➜  left-side-solution git:(main) ✗ cat test/data/input/object.calc
obj = fun(x) { x },
obj("name") = "John",
obj("age") = 42,
obj("greet") = fun(other) {
    write("I am "+obj("name")+
    ". I am "+obj("age")+
    " years old. Glad to meet you "+other)
},
obj("greet")("Juana")

When you run the former code you get the following output:

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/object.calc | node
I am John. I am 42 years old. Glad to meet you Juana

🚫

Notice how the obj method greet is able to access the properties of obj like name and age

Classes and OOP

The following code defines a sort of "class" Person that has a constructor that receives a name and an age. The class has a method greet that receives the other argument and writes a message to the console. We are using the semicolon notation that will be introduced in the section Currying and multiple arguments for functions of this lab.

test/data/input/object-template.calc

➜  left-side-solution git:(main) ✗ cat test/data/input/object-template.calc
Person = fun(name) {
    this = fun () { 0 },
    this("name") = name,
    this("greet") = fun(other) {
      write("I am "+this("name")+". Glad to meet you "+other)
    },
    fun(age) { # scope analysis must change
      this("age") = age, # this is not local to this function because it is a modification not a definition!!
      this
    }
},
john = Person("John"; 25),
john("greet")("Juana")

Notice that line 10 returns this which is why in line 13 the assignment john = Person("John"; 25) sets john to the object created by the constructor Person.

Once we are sure we have rightly modified the scope analysis to consider the fact that a(expression) = value is a modification but not a definition, we can proceed to the translation of the former code. Here is a potential translation of the former code:

test/data/expectedjs/object-template.js

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/object-template.calc 
#!/usr/bin/env node --stack-size=65500
const { functionObject, Complex, assign, write } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $Person, $john;
 
($Person = functionObject(function($name) {
    let $this;
 
    return (((
    $this = functionObject(function() { return Complex("0"); }), 
    assign($this, ["name"], $name)), 
    assign($this, ["greet"], functionObject(function($other) {
        return write("I am ".add($this("name")).add(". Glad to meet you ").add($other));
    }))), 
    functionObject(function($age) {
        return assign($this, ["age"], $age), $this;
    }))
}), 
$john = $Person("John")(Complex("25"))), 
$john("greet")("Juana");

When you run the former code (modified manually) you get the following output:

➜  functions-solution git:(array-map) ✗ node test/data/expectedjs/object-template.js
I am John. Glad to meet you Juana

Setters

Let us add a setAge method to the Personclass:

test/data/input/object-template-semicolon-3.calc

left-side-solution git:(main) ✗ cat test/data/input/object-template-semicolon-3.calc
Person = fun(name; age) {
    this = fun (x) { x },
    this("name") = name,
    this("age") = age, 
 
    this("setAge") = fun(newAge) {
      this("age") = newAge # if it is a setter changes the reference to the object
    },
    this
},
thom = Person("Thom"; 78),
thom("setAge")(80),
write(thom("name"); "is"; thom("age"))

Notice also that we are returning this at the end of the constructor. If you remove line 10 it will not work.

When you compile the former code you get the following Javascript code:

test/data/expectedjs/object-template-semicolon-3.js

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/object-template-semicolon-3.calc      
#!/usr/bin/env node --stack-size=65500
const { functionObject, assign, Complex, write } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $Person, $thom;
 
(($Person = functionObject(function($name) {
    return functionObject(function($age) {
        let $this;
 
        return ((($this = functionObject(function($x) {
            return $x;
        }), 
        assign($this, ["name"], $name)), 
        assign($this, ["age"], $age)), 
        assign($this, ["setAge"], functionObject(function($newAge) {
            return assign($this, ["age"], $newAge);
        }))), 
        $this;
    });
}), 
$thom = $Person("Thom")(Complex("78"))), 
$thom("setAge")(Complex("80"))), 
write($thom("name"), "is", $thom("age"));

that when run produces the following output:

➜  left-side-solution git:(main) bin/calc2js.mjs test/data/input/object-template-semicolon-3.calc | node
Thom is 80

To implement the setters we need that the code of assign receives the reference to the function to be passed by reference. That is the variable $thom has to change to receive the reference to the original function when is modified by assign. To make this possible I have to convert each function to a FunctionObject that is a class that wraps a function and allows the modification of the reference.

assign($this, ["setAge"], functionObject(function($newAge) {
            return assign($this, ["age"], $newAge);
        }));

Inheritance

Here is an example of how to implement inheritance in our language. It uses the semicolon notation that will be introduced in the section Currying and multiple arguments for functions and the bracket notation that will be introduced in an incoming lab. Arrays will be functions that map integers to their elements and strings to their corresponding methods.

test/data/input/inheritance.calc

Person = fun(name; age) {
    this = fun () { 0 },
    this("name") = name,
    this("greet") = fun(other) {
      write("I am "+this("name")+". Glad to meet you "+other)
    },
    this("age") = age, 
    this
},
 
Teacher = fun(name; age; subjects) {
    this = Person(name; age),
    this("subjects") = subjects,
    this
},
 
john = Teacher("John"; 69; ["PL"; "DMSI"]),
john("greet")("Juana"),
write(john("name");"teaches subject";john("subjects")(0))

When you run the former code you get the following output:

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/inheritance.calc | node
I am John. Glad to meet you Juana
John teaches subject PL

The FunctionObject class

A "callable object" or "Function object" (opens in a new tab) is a data structure that behaves as both an object and a function.

You can

access and assign properties obj.bar,
call methods obj.foo(), but also
call the object directly obj(), as if it were a function.

The direct call is like calling a method of obj which has access to the object’s properties through its this context.

The package callable-object (opens in a new tab) provides a simple implementation of a callable object in JavaScript.

See the repo ULL-ESIT-PL/callable-objects (opens in a new tab) for some examples.

Therefore we convert each function to a FunctionObject which has an attribute function storing the function and a method _call that is the method that is going to be called when the object is called directly:

src/FunctionObject.js

const CallableInstance = require("callable-instance");
 
class FunctionObject extends CallableInstance {
    constructor(a) {
        super("_call");
        this.function = a;
    }
 
    _call(arg) {
        let result = this.function(arg);
        return (typeof result == 'undefined') ? null : result;
    }
 
    toFunction() {
        return this.function;
    }
 
    toString() {
        return this.function.toString();
    }
}
 
function functionObject(a) {
    return new FunctionObject(a);
}
 
module.exports = { functionObject, FunctionObject };

The assign function

As we have seen the assign function receives

a function $f that is going to be modified,
an array of arguments cacheArgs like [ Complex("2"), Complex("3")] that correspond to the source nested calls f(2)(3)
the value to return Complex("8") in the example f(2)(3) = 8
the index i to recursively traverse the cacheArgs array.

This is a naive implementation of the assign function:

src/assign-simple.js

function assign(oF, cacheArgs, cacheValue) {
    let f;
    if (oF?.constructor?.name === "FunctionObject") {
        f = oF.toFunction();
    } else {
        f = oF;
    }
    oF.function = _assign(f, cacheArgs, cacheValue, 0);
    return oF;    
}
 
function _assign(f, cacheArgs, cacheValue, i) {
    let next = i+1;
    if (f.constructor.name == "ArrayFunction") { // Code for incoming lab
        f.assign(cacheArgs, cacheValue);         // not for this lab
        return f; 
    }
    let cacheArgument = cacheArgs[i];
 
    return function (...args) {
        let auxF = f;
 
        if (cacheArgument == null) {
            let error = new Error('Invalid null argument on left side of assignment');
            throw error;
        }
        if (args[0].equals && args[0]?.equals(cacheArgument) || args[0] == cacheArgument) {  
            if (cacheArgs.length === next) {
                return cacheValue;
            }
            auxF = f(...args);
            return _assign(auxF, cacheArgs, cacheValue, next)
        }
        return auxF(...args);
    }
}
 
module.exports = { assign };

Currying and multiple arguments for functions

We are going to introduce a notation of lists of identifiers separated by semicolons ; inside the parameter section of a function declaration. Correspondingly we also introduce list of semicolons separated expressions inside a function call. The following example illustrates its use:

test/data/input/fun-manyargs.calc

f = fun(x;y) {
  x+y
},
print(f(2;3)) # same as f(2)(3)

The translation shows how the function f is curryfied and converted onto a function of one argument that returns a function. In the same way f(2;3) is translated as f(2)(3):

test/data/expectedjs/fun-manyargs.js

➜  left-side-solution git:(main) bin/calc2js.mjs test/data/input/fun-manyargs.calc
 
#!/usr/bin/env node 
const { functionObject, print, Complex } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $f;
 
$f = functionObject(function($x) {
    return functionObject(function($y) {
        return $x.add($y);
    });
}), 
print($f(Complex("2"))(Complex("3")));

When you run the former code you get the following output:

➜  functions-solution git:(array-map) ✗ node test/data/expectedjs/fun-manyargs.js 
{ re: 5, im: 0 }

Here is a new version of the Person class that uses the semicolon notation:

test/data/input/object-template-semicolon.calc

Person = fun(name; age) {
    this = fun () { 0 },
    this("name") = name,
    this("greet") = fun(other) {
      write("I am "+this("name")+". Glad to meet you "+other)
    },
    this("age") = age, 
    this
},
john = Person("John"; 25),
john("greet")("Juana")

That when compiled

➜  functions-solution git:(array-map) ✗ bin/calc2js.mjs test/data/input/object-template-semicolon.calc -o test/data/expectedjs/object-template-semicolon.js

produces the following JavaScript code:

test/data/expectedjs/object-template-semicolon.js

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/object-template-semicolon.calc
#!/usr/bin/env node --stack-size=65500
const { functionObject, Complex, assign, write } = require("/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/src/support-lib.js"); 
/* End of support code */
 
let $Person, $john;
 
($Person = functionObject(function($name) {
    return functionObject(function($age) {
        let $this;
 
        return ((($this = functionObject(function() {
            return Complex("0");
        }), 
        assign($this, ["name"], $name)), 
        assign($this, ["greet"], functionObject(function($other) {
            return write("I am ".add($this("name")).add(". Glad to meet you ").add($other));
        }))), 
        assign($this, ["age"], $age)), 
        $this;
    });
}), 
$john = $Person("John")(Complex("25"))), 
$john("greet")("Juana");

When you run the former code you get the following output:

➜  functions-solution git:(array-map) ✗ node test/data/expectedjs/object-template-semicolon.js 
I am John. Glad to meet you Juana

Videos

2024/04/09

Herencia en calc. Como implantar el currying en funciones y llamadas.

2024/04/08

Clase del 08/04/2024. Tests: bin/test and .env. Scope analysis and the left side of an assignment. The assign function. Performance of the assign function

2024/04/03

Clase del 03/04/2024. Doubts and queries about lexer-generator. The FunctionObject class. Callable instances. First steps on the assign function

2024/04/02

Extending the assignment to functions: the left side lab

2024/03/20

Clase del 20/03/2024. Your workflow when adding a new feature to a translator

Clase del 13/03/2024. Building the Egg AST for 'ID apply'. Adding loops to the calculator language

Pruebas, Covering e Integración Continua

Escriba las pruebas, haga un estudio de cubrimiento usando c8 (opens in a new tab) y añada integración continua usando GitHub Actions.

Lea las secciones Testing with Mocha y Jest.

Publishing a package to the GitHub Registry

See the chapter Publishing a package to the GitHub Registry and the sections

One way to set GitHub as the registry is to add a publishConfig field to your package.json file

package.json

{
  "name": "@ull-esit-pl-2324/functions-name-ape1-ape2-aluXXX",
  "version": "1.2.0",
  "description": "A lab for PL. Adding Functions to our Calculator",
  "main": "src/transpile.js",
  "bin": {
    "calc2js": "./bin/calc2js.js"
  },
  "publishConfig": {
    "registry": "https://npm.pkg.github.com"
  },
  ...
}

I noticed many of you are having a hard time trying to publish the module to the GitHub Package Registry.

This class 2023/03/14 from 18:03 to to 35:00 may help to overcome the gotchas when publishing a private npm module in the github package registry.

Start to talk about publishing a module at minute 18:03.
How to get the GitHub token at minute 19:58
Providing the token to the npm client at minute 23:00
Issuing npm publish at minute 23:52
Associating the GitHub Organization ULL-ESIT-PL-2324 as a scope to the github registry at minute 28:13
From minute 34:25 and on, we discuss how to build a web site using a static generator like Vuepress and how to deploy it to GitHub Pages.

Documentación

Documente el módulo incorporando un README.md y la documentación de la función exportada usando JsDoc. Lea la sección Documenting the JavaScript Sources

Rubric

left-side Repos

Challenge: Performance of extended assignments

Consider the following input:

test/data/input/assign-performance.calc

n = Complex(commandLine(2)),  # number of assignments
if (n < 2) { n = 4 },         # if no argument is given or less than 2, n = 4
write(n;" repetitions"),
f = fun(x) { 0 },             # initial value of f
experiment = fun() {
    # Make assignments
    for(j=0;j<n;j=j+1) {
      f(j) = j
    },
    # Use assignments
    for(j=0;j<n;j=j+1) {
      result = f(j)
    }
 
},
performance("assign"; experiment) # measure the time spent in the experiment

that when executed gives the time in milliseconds spent in the function experiment. The number of assignments can be given as a command line argument.

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/assign-performance.calc -o test/data/actualjs/assign-performance.js
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js
4  repetitions
assign: 0.782ms
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 6
6  repetitions
assign: 0.887ms

Whe we use the algorithm described in the lab for the assignment

src/assign-simple.js

function assign(oF, cacheArgs, cacheValue) {
    let f;
    if (oF?.constructor?.name === "FunctionObject") {
        f = oF.toFunction();
    } else {
        f = oF;
    }
    oF.function = _assign(f, cacheArgs, cacheValue, 0);
    return oF;    
}
 
function _assign(f, cacheArgs, cacheValue, i) {
    let next = i+1;
    let cacheArgument = cacheArgs[i];
 
    return function (...args) {
        let auxF = f;
 
        if (cacheArgument == null) {
            let error = new Error('Invalid null argument on left side of assignment');
            throw error;
        }
        if (args[0].equals && args[0]?.equals(cacheArgument) || args[0] == cacheArgument) {  
            if (cacheArgs.length === next) {
                return cacheValue;
            }
            auxF = f(...args);
            return _assign(auxF, cacheArgs, cacheValue, next)
        }
        return auxF(...args);
    }
}
module.exports = { assign };

🚫

We get 5 secs for 100 assignments, 1 minute for 1000 assignments and a stack overflow 💥 for 10000 assignments:

➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 100 
100  repetitions
assign: 4.786ms
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 1000
1000  repetitions
assign: 59.203ms
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 10000
10000  repetitions
/Users/casianorodriguezleon/campus-virtual/2324/pl2324/practicas/left-side/left-side-solution/node_modules/complex.js/complex.js:1293
RangeError: Maximum call stack size exceeded

A trivial solution to the stack overflow problem is to increase the stack size¹:

➜  left-side-solution git:(main) ✗ bin/calc2js.mjs test/data/input/assign-performance.calc -o test/data/actualjs/assign-performance.js -n '-stack-size=65536'
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 10000
10000  repetitions
assign: 3.971s

The stack overflow dissapears, but the time is still too high.

The challenge is to improve the performance of the algorithm in src/assign-simple.js so that it can handle more assignments and work with smaller stacks.

Here we run an alternative implementation of the algorithm. We can see that it is 119 times faster than the original implementation. It also does not require an increase on the stack size:

src/assign-improved.js

➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 10000
10000  repetitions
assign: 33.386ms
➜  left-side-solution git:(main) ✗ node
> 3971/33.386 // we divide the previous time with the simple approach by the time with the improved approach
118.94207152698735

Here are the times for sizes 1e5 (0.2 seconds), 1e6 (1.2 seconds) and 1e7 (13 seconds) assignments:

➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 100000
100000  repetitions
assign: 182.074ms
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 1000000
1000000  repetitions
assign: 1.243s
➜  left-side-solution git:(main) ✗ test/data/actualjs/assign-performance.js 10000000
10000000  repetitions
assign: 13.078s

Here is a summary of the times:

size	1e5	1e6	1e7
time simple	💥 (overflow)	💥	💥
time cached	0.182s	1.243s	13.078s

The idea behind this version of the algorithm is to simply use a cache for the assignments.

We have added the option -n --node <nodeOptions> options for node.js,eg: '-n --stack-size=4096' (default: "") to our compiler: ↩

References

My old notes in memoization (opens in a new tab) of the fibonacci function in Ruby and
The wikipedia section on Memoization (opens in a new tab).
Memoization of the require in Egg (opens in a new tab)
memoize (opens in a new tab) npm package by Sindre Sorhus
Memoization of Multi-Parametered Functions in JavaScript (opens in a new tab) by Joseph Sikorski. Jul 14, 2017
The package callable-object (opens in a new tab) provides a simple implementation of a callable object in JavaScript.
See the repo ULL-ESIT-PL/callable-objects (opens in a new tab).

Pattern Matching Lexer Generator

Functions on the left side of an assignment

GoRace Experiment

Footnotes

Goal: Functions on the left side of an assignment

Introduction

Scope Analysis revisited

Modifying a function with nested calls on the left side

Nested calls on the left side and a function on the right side

Empty arguments on the left side

Types and symmetry

Consequences: Object Oriented Programming

Classes and OOP

Setters

Inheritance

The FunctionObject class

The assign function

Currying and multiple arguments for functions

Videos

2024/04/09

2024/04/08

2024/04/03

2024/04/02

2024/03/20

Pruebas, Covering e Integración Continua

Publishing a package to the GitHub Registry

Documentación

Rubric

left-side Repos

Challenge: Performance of extended assignments

Footnotes

References