Ricorsione in Boomerang e Nested Word Automata

A lens is a bidirectional program. Read from right to left it denotes a an ordinary function which maps inputs into outputs. Read from left to right it denotes an update translator which takes the input and the modified output and produces an updated input. Boomerang is a language based on a collection of lenses (combinators) which operate on ordered data (strings). It is based on the concept of resourcefulness, the correct use of keys associated to substrings of the input and the ouput. The goal of this work is to discuss how Boomerang could be equipped with a recursion combinator which allows string lenses with recursive structure (tree,...). Since in Boomerang all the combinators have a type which ensures totality (the lens is always defined on the input and output sets of the type), the recursion combinator must also have this propriety. While for the old combinators regular languages are exressive enough to represent types, for recursive combinator we need a more wide set in order to describe types. At the beginning the idea was that of using languages that could be transformed into Nested Word Language (NWL), since these languages have good proprieties and represent in a natural way tagged strings (HTML,...). These languages have a natural interpretation as NWL. We showed that decide wether a language could be transformed in a non-ambiguous way in a NWL is an undecidable problem and so we decided to use Context Free Language.

Una lens è un programma bidirezionale. Letto da destra a sinistra denota una funzione ordinaria che mappa gli input negli output. Letta da sinistra a destra denota un ``traduttore di update'' che prende come parametro un input e un output modificato e produce un nuovo input che riflette tali modifiche. Boomerang è un linguaggio basato su di una collezione di lenses (combinatori) che lavorano su dati ordinati (stringhe). Esso si basa sul concetto di resourcefulness, ovvero sul corretto uso di chiavi associate a sottostringhe dell'input e dell'output. Lo scopo di questo lavoro è discutere come Boomerang possa essere dotato di un combinatore di ricorsione che permetta l'utilizzo di lenses su stringhe con strutture ricorsive (alberi,...). Poichè in Boomerang tutti i combinatori attualmente esistenti hanno un tipo che ne assicura la totalità (la lente è sempre definita sui due insiemi di input e output del suo tipo), anche il combinatore di ricorsione deve avere questa proprietà. Mentre per i combinatori precedenti i linguaggi regolari sono sufficienti a rappresentare i tipi delle lenses, per un combinatore di ricorsione necessitiamo di un'insieme più ampio in grado di descrivere i tipi di dati su cui è definito questo combinatore. Inizialmente si era pensato di utilizzare linguaggi che possano essere trasformati in modo univoco in linguaggi Nested Word (NWL), dato che quest'ultimi godono di buone proprietà e rappresentano in modo naturale stringhe taggate (HTML,...). Questi linguaggi hanno una naturale interpretazione come Nested Words. Abbiamo però dimostrato che l'univocità della trasformazione da un NWL in cui le annotazioni sono state cancellate all'originale NWL è indecidibile e per questo si è deciso di utilizzare i linguaggi Context Free per descrivere i dati su cui opera l'operatore di ricorsione in quanto più espressivi (anche se con peggiori proprietà di chiusura).