Função aninhada - Nested function

Em programação de computador , uma função aninhada (ou procedimento aninhado ou sub - rotina ) é uma função que é definida dentro de outra função, a função envolvente . Devido a regras de escopo recursivo simples , uma função aninhada é invisível fora de sua função imediatamente envolvente, mas pode ver (acessar) todos os objetos locais (dados, funções, tipos, etc.) de sua função imediatamente envolvente, bem como de qualquer função (s) que, por sua vez, inclui essa função. O aninhamento é teoricamente possível em profundidade ilimitada, embora apenas alguns níveis sejam normalmente usados ​​em programas práticos.

Funções aninhadas são usadas em muitas abordagens de programação estruturada , incluindo as primeiras, como ALGOL , Simula 67 e Pascal , e também em muitas linguagens dinâmicas e funcionais modernas . No entanto, eles tradicionalmente não são suportados na família de linguagens C (originalmente simples).

Efeitos

As funções aninhadas assumem o escopo da função ou do bloco . O escopo de uma função aninhada está dentro da função envolvente, ou seja, dentro de um dos blocos constituintes dessa função, o que significa que ela é invisível fora desse bloco e também fora da função envolvente. Uma função aninhada pode acessar outras funções locais, variáveis, constantes, tipos, classes, etc. que estão no mesmo escopo ou em qualquer escopo fechado, sem passagem de parâmetro explícita, o que simplifica muito a passagem de dados para dentro e para fora da função aninhada. Isso normalmente é permitido para leitura e escrita.

As funções aninhadas podem, em certas situações (e linguagens), levar à criação de um encerramento . Se for possível para a função aninhada escapar da função envolvente, por exemplo, se as funções forem objetos de primeira classe e uma função aninhada for passada para outra função ou retornada da função envolvente, então um fechamento é criado e chamadas para esta função podem acessar o ambiente da função original. O quadro da função de fechamento imediato deve continuar ativo até que o último fechamento de referência morra e as variáveis ​​automáticas não locais referenciadas nos fechamentos não podem, portanto, ser alocadas na pilha . Isso é conhecido como o problema de funarg e é um dos principais motivos pelos quais as funções aninhadas não foram implementadas em algumas linguagens mais simples, pois complica significativamente a geração e a análise de código, especialmente quando as funções são aninhadas em vários níveis, compartilhando diferentes partes de seu ambiente.

Exemplos

Um exemplo de sintaxe Pascal (com ALGOL , Modula 2 , Oberon , Ada , etc. semelhante): 

function E(x: real): real;
    function F(y: real): real;
    begin
        F := x + y
    end;
begin
    E := F(3) + F(4)
end;

A função Festá aninhada em E. Observe que Eo parâmetro de xtambém é visível em F(como Fparte de E), enquanto xe ysão invisíveis fora Ee Frespectivamente.

Da mesma forma, em ML padrão: 

fun e (x : real) =
  let
    fun f y = x+y
  in
    f 3 + f 4
  end;

Uma maneira de escrever o mesmo exemplo na sintaxe Haskell : 

e :: Float -> Float
e x = f 3 + f 4 where f y = x + y

O mesmo exemplo na sintaxe GNU C (C estendido com funções aninhadas): 

float E(float x)
{
    float F(float y)
    {
        return x + y;
    }
    return F(3) + F(4);
}

Ordenação rápida

Um exemplo mais realista é esta implementação de quicksort : 

void sort(int *items, int size) {
    void quickSort(int first, int last) {
        void swap(int p, int q) {
            int tmp = items[p];
            items[p] = items[q];
            items[q] = tmp;
        }
        
        int partition() {
            int pivot = items[first], index = first;
            swap(index, last);
            for (int i = first; i < last; i++)
                if (items[i] < pivot)
                    swap(index++, i);
            swap(index, last);
            return index;
        }

        if (first < last) {
            int pivotIndex = partition();
            quickSort(first, pivotIndex - 1);
            quickSort(pivotIndex + 1, last);
        }
    }
    quickSort(0, size - 1);
}

Outro exemplo é a seguinte implementação do quicksort baseado em partição Hoare usando a sintaxe de expressão lambda do C ++ 11 : 

template<typename RandomAccessIterator>
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void {
	auto Partition = [&]() {
		//Hoare partition scheme
		auto &Pivot = *Begin;
		auto ForwardCursor = Begin;
		auto BackwardCursor = End - 1;
		auto PartitionPositionFound = false;
		auto LocatePartitionPosition = [&]() {
			while (*ForwardCursor < Pivot)
				++ForwardCursor;
			while (Pivot < *BackwardCursor)
				--BackwardCursor;
			if (ForwardCursor >= BackwardCursor)
				PartitionPositionFound = true;
			else
				Swap(*ForwardCursor, *BackwardCursor);
		};
		//Trivial helper function
		auto MoveOnAndTryAgain = [&]() {
			++ForwardCursor;
			--BackwardCursor;
		};
		//Brief outline of the actual partition process
		while (true) {
			LocatePartitionPosition();
			if (PartitionPositionFound)
				return BackwardCursor + 1;
			else
				MoveOnAndTryAgain();
		}
	};
	//Brief outline of the quicksort algorithm
	if (Begin < End - 1) {
		auto PartitionPosition = Partition();
		Sort(Begin, PartitionPosition);
		Sort(PartitionPosition, End);
	}
}

Propósito

As definições de função aninhadas lexicamente são uma forma de ocultar informações e são úteis para dividir tarefas procedimentais em subtarefas que são significativas apenas localmente. Isso evita confundir outras partes do programa com funções e variáveis ​​não relacionadas a essas partes.

Eles são normalmente usados ​​como funções auxiliares ou como funções recursivas dentro de outra função (como no exemplo quicksort acima). Isso tem o benefício estrutural de organizar o código, evita poluir o escopo e também permite que funções compartilhem estados facilmente. Como a função aninhada pode acessar variáveis ​​locais da função envolvente, o compartilhamento de estado é possível sem passar parâmetros para a função aninhada ou usar uma variável global , simplificando o código.

Em linguagens com funções aninhadas, as funções normalmente também podem conter constantes locais e tipos (além de variáveis locais , parâmetros e funções), encapsulados e ocultos da mesma maneira aninhada, em qualquer nível de profundidade. Isso pode aumentar ainda mais as possibilidades de estruturação do código.

Outros usos

Controle de fluxo

Funções aninhadas também podem ser usadas para fluxo de controle não estruturado , usando a instrução return para fluxo de controle geral não estruturado. Isso pode ser usado para um controle mais refinado do que é possível com outros recursos integrados da linguagem - por exemplo, pode permitir o encerramento antecipado de um loop for breakse não estiver disponível, ou o encerramento antecipado de um loop for aninhado se um multi -nível breakou exceções não estão disponíveis.

Funções de ordem superior

Artigo principal: Funções de ordem superior

Como na maioria das linguagens as funções são tipos de retorno válidos, é possível criar uma função aninhada que acessa um conjunto de parâmetros da função externa e tem essa função como o valor de retorno da função externa. Assim, é possível retornar uma função que está definida para cumprir uma determinada tarefa com pouco ou nenhum parâmetro adicional fornecido a ela, o que pode aumentar o desempenho de forma bastante significativa.

Alternativas

A principal alternativa para funções aninhadas em linguagens que não têm suporte para elas é colocar todas as funções e variáveis ​​relevantes em um módulo separado (arquivo) e expor publicamente apenas a função de wrapper de nível superior . Em C, isso geralmente será feito usando funções estáticas para encapsulamento e variáveis ​​estáticas para comunicação. Isso atinge o encapsulamento e o compartilhamento de estado, embora não seja a organização lógica dada pelo aninhamento lexical de funções, e tem o custo de ter um arquivo separado. Também não é possível em mais de um único nível.

Outra alternativa é compartilhar o estado entre as funções por meio de parâmetros de função, na maioria das vezes passando referências como argumentos para evitar o custo de cópia. Em C, isso geralmente é implementado por um ponteiro para uma estrutura que contém o contexto. Isso aumenta significativamente a complexidade das chamadas de função.

Em PHP e outras linguagens, a função anônima é a única alternativa: a função aninhada é declarada não como uma função normal, mas por referência, como uma variável local. Para usar variáveis ​​locais na função anônima, use closure .

línguas

Linguagens bem conhecidas que suportam funções aninhadas lexicamente incluem:

Linguagens funcionais

Na maioria das linguagens de programação funcionais , como Scheme, funções aninhadas são uma maneira comum de implementar algoritmos com loops. Uma função interna recursiva simples ( cauda ) é criada, que se comporta como o loop principal do algoritmo, enquanto a função externa executa ações de inicialização que precisam ser feitas apenas uma vez. Em casos mais complexos, várias funções recursivas mutuamente podem ser criadas como funções internas.

Alguns idiomas sem suporte direto

Certas linguagens não têm suporte sintático e semântico direto para implementar funções aninhadas. No entanto, para alguns deles, a ideia de funções aninhadas pode ser simulada com algum grau de dificuldade por meio do uso de outras construções de linguagem. As seguintes linguagens podem aproximar funções aninhadas por meio das respectivas estratégias:

  • C ++
    • antes de C ++ 11: permite a definição de classes dentro de classes, fornecendo a capacidade de usar métodos de classe de maneira semelhante a funções aninhadas em um nível (consulte Objeto de função em C ++ ).
    • desde C ++ 11: usando expressões lambda como o exemplo quicksort acima.
  • Eiffel proíbe explicitamente o aninhamento de rotinas. Isso é para manter a linguagem simples e também permite a convenção de usar uma variável especial, Resultado , para denotar o resultado de uma função (de retorno de valor).
  • Visual Basic , usando métodos anônimos ou expressões lambda.
  • Java , usando expressões lambda (consulte Funções anônimas em Java ) (desde Java 8) ou por meio de uma solução alternativa que consiste em uma classe anônima contendo um único método. Uma classe nomeada declarada local para um método também pode ser usada.

Implementação

Veja também: Teste de homem ou menino

A implementação de funções aninhadas pode ser mais envolvente do que pode parecer, pois uma referência a uma função aninhada que faz referência a variáveis ​​não locais cria um encerramento . Por esse motivo, funções aninhadas não são suportadas em algumas linguagens como C, C ++ ou Java, pois isso torna os compiladores mais difíceis de implementar. No entanto, alguns compiladores os suportam, como uma extensão específica do compilador. Um exemplo bem conhecido disso é a implementação GNU C de C que compartilha código com compiladores para linguagens como Pascal, Ada e Modula.

Acesso de objetos não locais

Existem várias maneiras de implementar procedimentos aninhados em uma linguagem com escopo léxico, mas a maneira clássica é a seguinte:

Qualquer objeto não local , X, é alcançado por meio de links de acesso nos frames de ativação na pilha da máquina. O chamador, C, auxilia o procedimento chamado, P, empurrando um link direto para a última ativação do encapsulamento lexical imediato de P, (P), antes da chamada em si. P pode então encontrar rapidamente a ativação correta para um determinado X seguindo um número fixo (P.depth - X.depth) de links (normalmente um pequeno número).
O chamador cria este link direto (ele mesmo) seguindo C.depth - P.depth + 1 links mais antigos, levando à ativação mais recente de (P) e, em seguida, fazendo uma ponte temporária sobre eles com um link direto para essa ativação; o link posteriormente desaparece junto com P, por meio do qual os links mais antigos abaixo dele podem ser usados ​​novamente.
Observe que P é visível para, e pode, portanto, ser chamado por C se (P) = C / (C) / ((C)) / etc.

Este método original é mais rápido do que pode parecer, mas, no entanto, é frequentemente otimizado em compiladores modernos práticos (usando monitores ou técnicas semelhantes).

Outra maneira de implementar funções aninhadas que é usado por alguns compiladores é converter ("levantar") funções aninhadas em funções não aninhadas (onde parâmetros extras, ocultos substituem os links de acesso) usando um processo conhecido como levantamento de lambda durante um estágio intermediário na compilação.

Funciona como valores

Para que as funções locais com não locais com escopo léxico sejam passados ​​como resultados, o código de tempo de execução da linguagem também deve passar implicitamente o ambiente (dados) que a função vê dentro de sua função de encapsulamento, de modo que seja alcançável também quando a ativação atual do função não existe mais. Isso significa que o ambiente deve ser armazenado em outra área de memória (as partes subsequentemente recuperadas de) uma pilha de execução baseada em cronologia, o que, por sua vez, implica em algum tipo de alocação de memória dinâmica livre . Muitas linguagens baseadas em Algol mais antigas (ou dialetos delas), portanto, não permitem que funções locais que acessam não locais sejam passadas como valores de retorno, ou não permitem funções como valores de retorno, embora a passagem de tais funções como argumentos ainda possa ser possível.

Pilhas sem execução

Pelo menos uma implementação de funções aninhadas causa uma perda de pilhas não executadas (pilha NX) . A implementação da função aninhada do GCC chama funções aninhadas por meio de uma instrução de salto colocada na pilha da máquina em tempo de execução. Isso requer que a pilha seja executável.

Nenhuma pilha de execução e funções aninhadas são mutuamente exclusivas no GCC. Se uma função aninhada for usada no desenvolvimento de um programa, o NX Stack será perdido silenciosamente. O GCC oferece o aviso -Wtrampoline para alertar sobre a condição.

O software desenvolvido com o Secure Development Lifecycle geralmente não permite o uso de funções aninhadas neste compilador específico (GCC) devido à perda de NX Stacks.

Veja também

Notas

Referências

links externos