Nested function | EPFL Graph Search

In computer programming, a nested function (or nested procedure or subroutine) is a function which is defined within another function, the enclosing function. Due to simple recursive scope rules, a nested function is itself invisible outside of its immediately enclosing function, but can see (access) all local objects (data, functions, types, etc.) of its immediately enclosing function as well as of any function(s) which, in turn, encloses that function. The nesting is theoretically possible to unlimited depth, although only a few levels are normally used in practical programs. Nested functions are used in many approaches to structured programming, including early ones, such as ALGOL, Simula 67 and Pascal, and also in many modern dynamic languages and functional languages. However, they are traditionally not supported in the (originally simple) C-family of languages. Effects Nested functions assume function scope or block scope. The scope of a nested function is inside the

Compilation Techniques for Incremental Collection Processing

Daniel Lupei

Many map-reduce frameworks as well as NoSQL systems rely on collection programming as their interface of choice due to its rich semantics along with an easily parallelizable set of primitives. Unfortunately, the potential of collection programming is not entirely fulfilled by current systems as they lack efficient incremental view maintenance (IVM) techniques for queries producing large nested results. This comes as a consequence of the fact that the nesting of collections does not enjoy the same algebraic properties underscoring the optimization potential of typical collection processing constructs. We propose the first solution for the efficient incrementalization of collection programming in terms of its core constructs as captured by the positive nested relational calculus (NRC+) on bags (with integer multiplicities). We take an approach based on delta query derivation, whose goal is to generate delta queries which, given a small change in the input, can update the materialized view more efficiently than via recomputation. More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify IncNRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incrementalmaintenance for NRC+ is within the complexity class NC0 and we showcase how Recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+ . Existing systems are also limited wrt. the size of inner collections that they can effectively handle before running into severe performance bottlenecks. In particular, in the face of nested collections with skewed cardinalities developers typically have to undergo a painful process of manual query re-writes in order to ensure that the largest inner collections in their workloads are not impacted by these limitations. To address these issues we developed SLeNDer, a compilation framework that given a nested query generates a set of semantically equivalent (partially) shredded queries that can be efficiently evaluated and incrementalized using state of the art techniques for handling skew and applying delta changes, respectively. The derived queries expose nested collections to the same opportunities for distributing their processing and incrementally updating their contents as those enjoyed by top-level collections, leading on our benchmark to up to 16.8x and 21.9x speedups in terms of offline and online processing, respectively. In order to enable efficient IVM for the increasingly common case of collection programming with functional values as in Links, we also discuss the efficient incrementalization of simplytyped lambda calculi, under the constraint that their primitives are themselves efficiently incrementalizable.

EPFL2017

On Decentralized Navigation Schemes for Coordination of Multi-Agent Dynamical Systems

Denis Gillet, Hajir Roozbehani, Sylvain Rudaz

Coordination of autonomous non-point agents in four-way crossings is studied in this work. A control scheme based on artiﬁcial potential functions is proposed in order to coordinate holonomic agents whose aim is to pass through an intersection while avoiding collisions. To do so, the agents are provided with a decentralized navigation function in which the goal and collision functions are decoupled. The local function deﬁned on each agent requires no global knowledge on the desired destination of other agents. Furthermore, a reachability analysis via Lyapunov functions is proposed in order to guarantee marginal stability in our case study. In addition, conﬂict-free navigation and convergence properties are veriﬁed in simulation.

2009

Nonlocal plasticity models for localized failure

Simon Rolshoven

In quasi-brittle materials such as concrete, failure is preceded by highly localized deformation patterns. Localized failure is caused by strain softening, which cannot be described by classical local models, because they lack a length scale. Mathematically, the use of such models leads to ill-posed boundary value problems. If properly formulated, nonlocal models can provide a sound description of strain softening and model the complete failure process of quasi-brittle materials. A bifurcation analysis is performed for a number of nonlocal plasticity models of the gradient and integral type, and the load-displacement response up to complete failure is computed. The nonlocal models are constructed mainly as enhancements of the standard smallstrain, rate-independent, isotropic local plasticity model. Most nonlocal models respond in a physically appropriate manner at initial bifurcation, but for some models, the plastic zone widens at later stages of the loading process, and stresses remain at a spuriously high level. For the integral format of two nonlocal models selected for further development, the VermeerBrinkgreve model and the ductile damage model, the bifurcation analysis is extended to hardening and the two-dimensional, plane strain setting. For both models, the enhancement is based on a modified hardening law, which depends in a specific way on the local hardening variable and its nonlocal counterpart. The analysis determines the range of material parameters for which the solution is regular and provides an analytical expression for the initial distribution of the rate of plastic strain. The use of the Vermeer-Brinkgreve model is restricted to softening, while the ductile damage model can be used for hardening and softening. An efficient and robust iterative numerical algorithm for the stress return of integral-type nonlocal models that use the local and nonlocal hardening variable in the yield function is developed and implemented. Due to weighted averaging, the stress return is a coupled nonlinear complementarity problem. It is solved by a Jacobi-like iterative technique, derived in a rigorous manner for a special case and generalized based on a physical interpretation of the resulting equations. In view of the numerical modeling of concrete, the nonlocal enhancement is applied to plasticity models with pressure-dependent yield functions and non-associated flow rules. Simulations of laboratory tests demonstrate that the nonlocal model regularizes localization due to softening and non-associated plastic flow. Neither the load-displacement response nor the propagation of the process zone depend in a spurious manner on the computational grid. For eccentric compression of a prismatic column under plane strain conditions, the trend for the size effect on structural strength and post-peak response is correctly predicted.