λόγος and the Rise of Turtle Graphics

Logos é uma palavra forte de origem grega, ela pode significar razão, palavra ou discurso. Os próprios gregos foram responsáveis pela Trigonometria, cuja etimologia é a composição das palavras trigōnon (triângulo) e metron (medida) – algo como o estudo das medidas do triângulo (3 lados e 3 ângulos). Eles também foram responsáveis pelas inserções da Geometria (γεωμετρία = terra + medida) Euclidiana. Ambas as disciplinas são ramificações da Matemática, sendo que elas, juntamente com Análise Vetorial e Quaternion são os elementos fundamentais da Matemática para Computação Gráfica.

Escola de Atenas e os Elementos de Euclides

Se juntarmos todos estes ingredientes, misturarmos e adicionarmos algumas palavras mágicas (spells) – dentro de contexto da Computação, obviamente. Podemos extrair um produto fundamental composto por um software gráfico e educacional cujo “logo” (de logotipo) é uma tartaruga.

Sim, é sobre isto mesmo que estou falando, da linguagem de programação Logo. Que possui uma fundação, que a promove: Logo Foundation. O mais interessante, é que Logo é influenciada pela linguagem de John McCarthy, e ele dispensa apresentação. Fora isto, existe outra ferramenta educacional criada pela Microsoft, o Small Basic, que promove a linguagem Basic.

O Basic aquele que deixou Gates e Allen famosos. E também foi minha primeira linguagem de programação (que com o passar do tempo houve uma relação entre amor e ódio, hoje existe muito respeito para com ela). O ambiente do Microsoft Small Basic possui um objeto chamado Turtle, que permite você fazer a mesma coisa que um ambiente Logo, só que em Basic – muito recomendado para a garotada, ou para os profissionais que ainda acham que programar para SharePoint (ou qualquer outro produto) é programar. (Nada pessoal, com SharePoint foi apenas uma escolha aleatória baseado em popularidade e falácia, poderia ser BizTalk, sei lá ).

The rise of Turtle Graphics

Há duas semanas, no mesmo dia que o Fates Warning tocou no Brasil, tive a oportunidade de ministrar uma palestra sobre Scala. E uma das minhas ideias era criar um exemplo especial fora do contexto do Scala. (O Fates Warning é uma das minhas bandas favoritas desde a adolescência).

O exemplo especial foi construir um ambiente de Turtle Graphics para Windows usando C++, Direct2D, Java e Scala. E estendi este exemplo para minha segunda linguagem favorita, o F#. Ou seja, programei o engine e seu modelo de scripting compatíveis com a JVM e com a CLR.

Na verdade, todo este trabalho surgiu pela oportunidade da palestra (Palestra Fundamentos de Scala). No entanto, criar este ambiente era uma idéia antiga, impulsionada pelo livro que está ai em cima: An Integrated Introduction to Computer Graphics and Geometric Modeling de Ronald Goldman. Neste livro, ele começa dizendo algo do tipo: “vamos começar aprender Computação Gráfica e sua Matemática usando o Turtle Graphics”. Assim, ele sugere o uso do Logo ou que você crie seu ambiente. Bem, eu optei pelo segundo, seguindo meu instinto de programador C++.

Após fazer um rápido protótipo com Excel para validar as equações trigonométricas, li rapidamente a documentação do Direct2D para extrair o que eu precisava codificar e sai codificando. Com engine finalizado, parti para a parte do scripting e fiz uma coisa inédita – usei Java Native Interfaces (JNI), para expor o código nativo para Scala – sinceramente, foi bem tranquilo e divertido – e para aqueles que gostariam de saber: Sim, estou programando em Java, afinal (agora) sou um programador sem fronteiras! A mesma coisa eu fiz para o F#, que no caso pode usar P/Invoke diretamente.

Camada de interoperabilidade do scripting com o Java:

import java.nio.ByteBuffer;

final class JNITurtle
{
    private native ByteBuffer create();
    private native void rotate(ByteBuffer hTurtle, float angle);
    private native void resize(ByteBuffer hApp, float size);
    private native void move(ByteBuffer hApp, int distance);
    private native void speed(ByteBuffer hApp, int value);
    private native void destroy(ByteBuffer hApp);

    private boolean disposed;
    private ByteBuffer hTurtle;

    JNITurtle()
    {
        disposed = false;
        hTurtle = create();
    }

    static
    {
        System.loadLibrary("Turtle");
    }

    public void rotate(float angle)
    {
        rotate(hTurtle, angle);
    }

    public void resize(float size)
    {
        resize(hTurtle, size);
    }

    public void move(int distance)
    {
        move(hTurtle, distance);
    }

    public void speed(int value)
    {
        speed(hTurtle, value);
    }

    public void dispose()
    {
        if(!disposed)
        {
           disposed = true;
           destroy(hTurtle);
        }
    }

    protected void finalize()
    {
        dispose();
    }
}

Camada de interoperabilidade do scripting com o F#:

namespace global

open System
open System.Runtime.InteropServices

module private API =
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern nativeint create()
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern void rotate(nativeint hApp, float32 angle)
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern void resize(nativeint hApp, float32 size)
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern void move(nativeint hApp, int distance)
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern void speed(nativeint hApp, int distance)
    [<DllImport(@"Turtle.dll", CallingConvention = CallingConvention.Cdecl)>]
    extern void destroy(nativeint hApp)

[<Sealed>]
type private PInvokeTurtle() =
    let mutable disposed = false
    let mutable hTurtle = API.create()

    override this.Finalize() = this.close()

    member this.rotate(angle: float32) = API.rotate(hTurtle, angle)

    member this.resize(size: float32) = API.resize(hTurtle, size)

    member this.move(distance: int) = API.move(hTurtle, distance)

    member this.speed(value: int) = API.speed(hTurtle, value)

    member private this.close() = 
        if not disposed then 
            disposed <- true
            API.destroy(hTurtle)

    interface IDisposable with
        member this.Dispose() = GC.SuppressFinalize(this); this.close()

Estes trechos de código interagem com a fachada que exporta o modelo de scripting: jnimain.cpp e dllmain.cpp do código nativo. Tanto o JNITurtle quanto o PInvokeTurtle implementam suas estratégias para liberação de recursos via dispose pattern.

jnimain.cpp:

#include "scriptable.hpp"

#include <jni.h>

extern "C" 
{
    JNIEXPORT jobject JNICALL Java_JNITurtle_create(JNIEnv* env, jobject)
    {
        return env->NewDirectByteBuffer(scriptable::create(), 0);
    }

    JNIEXPORT void JNICALL Java_JNITurtle_rotate(JNIEnv* env, jobject, jobject hTurtle, jfloat angle)
    {
        auto turtlePtr = reinterpret_cast<scriptable::TurtlePtr>(env->GetDirectBufferAddress(hTurtle));
        scriptable::rotate(turtlePtr, angle);
    }

    JNIEXPORT void JNICALL Java_JNITurtle_resize(JNIEnv* env, jobject, jobject hTurtle, jfloat size)
    {
        auto turtlePtr = reinterpret_cast<scriptable::TurtlePtr>(env->GetDirectBufferAddress(hTurtle));
        scriptable::resize(turtlePtr, size);
    }

    JNIEXPORT void JNICALL Java_JNITurtle_move(JNIEnv* env, jobject, jobject hTurtle, jint distance)
    {
        auto turtlePtr = reinterpret_cast<scriptable::TurtlePtr>(env->GetDirectBufferAddress(hTurtle));
        scriptable::move(turtlePtr, distance);
    }

    JNIEXPORT void JNICALL Java_JNITurtle_speed(JNIEnv* env, jobject, jobject hTurtle, jint speed)
    {
        auto turtlePtr = reinterpret_cast<scriptable::TurtlePtr>(env->GetDirectBufferAddress(hTurtle));
        scriptable::speed(turtlePtr, speed);
    }

    JNIEXPORT void JNICALL Java_JNITurtle_destroy(JNIEnv* env, jobject, jobject hTurtle)
    {
        auto turtlePtr = reinterpret_cast<scriptable::TurtlePtr>(env->GetDirectBufferAddress(hTurtle));
        scriptable::destroy(turtlePtr);
    }
}

dllmain.cpp:

#include "scriptable.hpp"

extern "C"
{
    __declspec(dllexport) scriptable::TurtlePtr create()
    {
        return scriptable::create();
    }

    __declspec(dllexport) void rotate(scriptable::TurtlePtr hTurtle, float angle)
    {
        scriptable::rotate(hTurtle, angle);
    }

    __declspec(dllexport) void resize(scriptable::TurtlePtr hTurtle, float size)
    {
        scriptable::resize(hTurtle, size);
    }

    __declspec(dllexport) void move(scriptable::TurtlePtr hTurtle, int distance)
    {
        scriptable::move(hTurtle, distance);
    }

    __declspec(dllexport) void speed(scriptable::TurtlePtr hTurtle, int value)
    {
        scriptable::speed(hTurtle, value);
    }

    __declspec(dllexport) void destroy(scriptable::TurtlePtr hTurtle)
    {
        scriptable::destroy(hTurtle);
    }
}

Você poderá carregar o Turtle.dll (o engine do Turtle Graphics) nos respectivos ambientes REPL (F# e Scala) usando uma fachada de código gerenciado, no meu caso TurtleFSharp.dll e turtle.jar.

E com isto, produzir uma sequência de riscos variados, ou seja, desenhos:

Aqui um exemplo de script em Scala:

Se tiver curiosidade. A Turtle.dll, o engine do meu Turtle Graphics, é composto das seguintes dependências:

D2D1.DLL é o Direct2D, MSCRV100.DLL é a C Runtime Library (CRT) do Visual C++ 10 e MSVCP100.DLL é a Standard C++ Library (SCL) do Visual C++ 10. O resto já é conhecido do sistema operacional Windows.

Se quiser digerir a parte que interage com o Direct2D, você encontrará no program.cpp definições como:

Construtor e os recursos a serem utilizados (estes caras que precisarão ser liberados pela ação de dispose):

Inicializador da Janela:

O message loop:

Método que desenha o caminho da tartaruga:

O “renderizador”:

Responsável por carregar o “cursor” da tartaruga:

As funções matemáticas de auxilio:

E o componente de script:

Enfim, vai encontrar algumas pérolas.

Faça o download do código fonte e binário do Turtle Graphics e assim como eu divirta-se. Na verdade, acho que você vai preferir mesmo o Small Basic ou o Logo, mas isto não é mais problema meu – mas o meu funciona nos REPLs do Scala e do F# (e C#, quando o Roslyn estiver ok).

Polimorfismo, polymorphism, πολυμορφισμού, …

Polimorfismo, já refletiu sobre ele? (no sentido de pensar, não é necessário usar Reflector ou algo parecido). Certamente, a linguagem de programação que você usa, possui uma ou mais formas de manifestação deste recurso.

A definição da palavra polimorfismo conecta com a palavra pleomorfismo, um termo usado na Biologia – isto significa: “a ocorrência de duas ou mais forma no ciclo de vida de um organismo”.

Se assim como eu, você deseja simplificar sua vida, assuma que as palavras poly + morph, ambas de origem grega (polýs + morphos), podem representar muitas + forma. Quando contextualizadas pode significar a capacidade de alguma coisa (função, tipo de dado, instância, …) assumir muitas formas.

A minha idéia não é definir formalmente o que é polimorfismo (mesmo porque este assunto poderia ser polêmico, e eu não estou muito afim de discussão conceitual). Mas, a idéia é mostrar livremente algumas manifestações do “muitas formas” no contexto aplicado a Programação de Software, mesmo se tal recurso não for formalmente categorizado como polimorfismo.

Uma das manifestações do polimorfismo é através de Dynamic Dispatching, onde existe um mecanismo de passagem de mensagem resolvido em tempo de execução. Quando isto ocorre, existe uma espécie de contrato entre o caller e o callee. Neste caso, é esperado um certo número de argumentos e retorno compartilhados por um nome. Alguns exemplos deste tipo de cenário, seria os serviços do Windows Communication Foundation (WCF) ou o modelo de atores do Erlang – em linhas gerais, eles recebem uma requisição (request) através de um nome roteado internamente (endpoint no WCF, identifier num receiver no Erlang) e respondem (response ou reply) ou ignoram tal chamada.

Sobre dynamic dispatching, não posso deixar de citar uma das implementações mais populares atualmente: Objective-C. A passagem de mensagem ocorre através da notação [receiver message], message contempla o método (selector) a ser chamado e seus argumentos (actual parameters). Embora o C exerceu forte influência sobre o Objective-C, foi do Smalltalk que ele baseou suas extensões de Orientação a Objetos e o mecanismo de passagem de mensagem.

No exemplo apresentado, isto está materializado na chamada da função callConvert. Note que, ao contrário do C++, C# ou Java, as instâncias chamadas não possuem vinculos de herança, exceto pelo NSObject que é obrigatório para suportar o message passing (objc_msgSend). Então desde que uma instância suporte tal contrato, ela poderá ser chamada e responderá com sucesso, senão responderá com falha e retornará um valor default (note o comportamento das chamadas no painel inferior direito da figura). Isto não combina com Duck Typing? (por enquanto, vamos deixar o pato de lado…)

#import <Foundation/Foundation.h>
//Sample provided by Fabio Galuppo
const float PI = 3.14159265f;

@interface Radians2Degree : NSObject
{
}

-(float) Convert:(float)value;
@end

@implementation Radians2Degree
-(float) Convert:(float)value
{
    return 180 * (value / PI);
}
@end

@interface Degree2Radians : NSObject
{
}

-(float) Convert:(float)value;
@end

@implementation Degree2Radians
-(float) Convert:(float)value
{
    return PI * (value / 180);
}
@end

float callConvert(id receiver, float value)
{
    return [receiver Convert:value];
}

int main(int argc, const char* argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];    

    Radians2Degree* r2d = [[Radians2Degree alloc] init];
    Degree2Radians* d2r = [[Degree2Radians alloc] init];

    NSLog(@"2PI in degrees == %f\n", [r2d Convert:(2 * PI)]);
    NSLog(@"360 in radians == %f\n", [d2r Convert:(360)]);
    NSLog(@"PI in degrees == %f\n", [r2d Convert:([d2r Convert:(180)])]);
    NSLog(@"180 in radians == %f\n", [d2r Convert:([r2d Convert:(PI)])]);

    NSLog(@"(1/2)PI in degrees == %f\n", callConvert(r2d, PI / 2));
    NSLog(@"90 in radians == %f\n", callConvert(d2r, 90));

    NSLog(@"270 in radians == %f\n", callConvert(nil, 270));

    [pool release];

    return 0;
}

Dado uma classe X e outra Y que não se correspondem diretamente, seria possível encontrar dynamic dispatching em outras linguagens? Certamente! A linguagem C# (na verdade a Common Language Runtime – CLR) suporta Invoke via reflection desde a versão 1.0. Porém, usar reflection para isto é muito chato e irritante. No entanto, para melhor suportar este mecanismo, o C# 3.0 introduziu a palavra chave dynamic. O compilador + CLR fazem “a mágica” acontecer, veja:

using System;

//Sample provided by Fabio Galuppo

class Program
{
    sealed class X
    {
        public String M(String value){ return value.ToUpper(); }
    }

    sealed class Y
    {
        public String M(String value)
        {
            char[] temp = value.ToCharArray();
            Array.Reverse(temp);
            return new String(temp);
        }
    }

    sealed class Z : System.Dynamic.DynamicObject
    {
        Func<String, String> DefaultResult_ = s => String.Empty;

        public override bool TryGetMember(System.Dynamic.GetMemberBinder binder, out object result)
        {
            result = DefaultResult_;
            return true;
        }
    }

    static String Selector(dynamic id, String value)
    {
        String result = String.Empty;

        try
        {
            result = id.M(value);
        }
        catch(Microsoft.CSharp.RuntimeBinder.RuntimeBinderException){}

        return result;
    }

    static void Main(string[] args)
    {
        Action<dynamic, String> m = (id, value) => Console.WriteLine("{0} -> {1}", value, Selector(id, value));

        m(new X(), "Hello");
        m(new Y(), "World");
        m(new object(), "Something");
        m(new Z(), "Something");

        Console.ReadLine();
    }
}

O método estático Selector invoca dinamicamente um método chamado M que recebe uma String cujo responde uma String (em destaque o contrato da operação). O comportamento é exatamente igual ao mecanismo de passagem de mensagem do Objective-C! Exceto que no Objective-C, o resultado retornado para uma instância cujo não possui um contrato compatível é o valor default da operação. Já no C# ocorre uma exceção pomposa: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException. Se desejar ter o mesmo comportamento do Objective-C (retornar o valor default), é necessário criar um interceptador, como a classe Z do exemplo.

Uma reflexão sobre notação:

Objective-C: [receiver Convert: value To: RADIANS];

C#: receiver.Convert (value, to = RADIANS);

Assim como as derivadas possuem suas diversas notações (da/dx – Leibniz, å – Newton) , o mecanismo de passagem de mensagem também possui tal notação baseado no gosto e expressão de seus criadores (Brad Cox, Anders Hejlsberg).

Continuando, tudo isto soou como Late Binding, não é mesmo? E late binding nos remete aos anais do Component Object Model (COM). O que seria do COM sem ele? (talvez a não existência de programadores Visual Basic, pensando bem…, deixa para lá… brincadeira – Visual Basic é uma nobre linguagem de programação que sofre preconceito de programadores elitistas, porém se usada pelas pessoas certas, podem fazer coisas muito legais) .

Com toda esta gloriosa volta do COM (WinRT, o novo COM), seria um bom momento para revisitá-lo. Focando no late binding com Active Template Library (ATL) e C++:

COM IS LOVE by Developmentor in their golden years (Don Box and team)

Eu ainda tenho a camiseta que eles distribuiam nos eventos.

O COM tem seu mecanismo de dynamic dispatching implementado em termos da interface IDispatch. ATL ajuda muito, tanto na construção do componente suportando late binding, bem como no seu consumo. Tudo relacionado aos componentes COM é dependente de interfaces, e estas por sua vez são descritas no código fonte (C++, por exemplo) e na interface definition language (IDL). Abaixo temos os melhores momentos da construção de 2 componentes COM suportando IDispatch (XType e YType):

class ATL_NO_VTABLE CXType :
    public CComObjectRootEx<CComMultiThreadModel>,
    public CComCoClass<CXType, &CLSID_XType>,
    public IDispatchImpl<IXType, &IID_IXType, &LIBID_InvokeMeLib, 1, 0>
{
public:
…

BEGIN_COM_MAP(CXType)
    COM_INTERFACE_ENTRY(IXType)
    COM_INTERFACE_ENTRY(IDispatch)
END_COM_MAP()

…

public:
    STDMETHOD(M)(BSTR value, BSTR* result);
};

#include "XType.h"

STDMETHODIMP CXType::M(BSTR value, BSTR* result)
{
    CComBSTR c(value);

    HRESULT hr = c.ToUpper();
    if(SUCCEEDED(hr))
    {
        *result = c;
        return S_OK;
    }

    return hr;
}

class ATL_NO_VTABLE CYType :
    public CComObjectRootEx<CComMultiThreadModel>,
    public CComCoClass<CYType, &CLSID_YType>,
    public IDispatchImpl<IYType, &IID_IYType, &LIBID_InvokeMeLib, 1, 0>
{
public:
…

BEGIN_COM_MAP(CYType)
    COM_INTERFACE_ENTRY(IYType)
    COM_INTERFACE_ENTRY(IDispatch)
END_COM_MAP()

…

public:
    STDMETHOD(M)(BSTR value, BSTR* result);
};

#include "YType.h"

STDMETHODIMP CYType::M(BSTR value, BSTR* result)
{
    CComBSTR c(value);

    USES_CONVERSION;

    char* x = OLE2A(c);
    strrev(x);
    *result = CComBSTR(x);

    return S_OK;
}

As classes CXType e CYType do exemplo ATL/COM/C++ imitam as classes X e Y, respectivamente, implementadas no C#. Então, você leitor conhecedor do C# (se não conhece, recomendo fortemente este livro), poderá mapear tais recursos e tirar suas conclusões.

O consumo do componente e a chamada late binding feita através de Invoke (via Selector) são mostradas na figura abaixo:

No exemplo, está em destaque o comportamento de uma chamada com contrato não suportado, onde a resposta (HRESULT) é Unknown name. O CComPtr<IDispatch> é uma especialização (usando o vocabulário do C++, isto quer dizer um template specialization) que ajuda MUITO as chamadas via Invoke (e outros).

#import "..\\..\\InvokeMe\\Debug\\InvokeMe.dll" raw_interfaces_only named_guids no_namespace

#include <atlbase.h>

#include <iostream>

//Sample provided by Fabio Galuppo

HRESULT Selector(CComPtr<IDispatch>& id, const CComBSTR& value, CComBSTR& result)
{
    CComVariant vValue(value), vResult;
    HRESULT hr = id.Invoke1(OLESTR("M"), &vValue, &vResult);
    if(SUCCEEDED(hr)) result = vResult.bstrVal;
    return hr;
}

int main(int argc, char* argv[])
{
    CoInitialize(NULL);
    {
    HRESULT hr = E_FAIL;

    CComPtr<IDispatch> x, y;    

    auto m = [](CComPtr<IDispatch>& id, const CComBSTR& value)
    {
        CComBSTR result;
        USES_CONVERSION;
        HRESULT hr = Selector(id, value, result);
        std::cout << OLE2CA(value) << " -> " << (SUCCEEDED(hr) ? OLE2CA(result) : "") << std::endl;
    };

    hr = x.CoCreateInstance(CLSID_XType, NULL, CLSCTX_ALL);
    if(SUCCEEDED(hr))
        m(x, CComBSTR("Hello"));

    hr = y.CoCreateInstance(CLSID_YType, NULL, CLSCTX_ALL);
    if(SUCCEEDED(hr))
        m(y, CComBSTR("World"));

    CComPtr<IDispatch> z;
    z.CoCreateInstance(OLESTR("Shell.Explorer"), NULL, CLSCTX_ALL);
    if(SUCCEEDED(hr))
        m(z, CComBSTR("Something"));
    }
    CoUninitialize();

    std::cin.get();
}

Compare o método Selector do C# com a função Selector do C++, elas fazem a mesma tarefa: invocam dinamicamente um método (função ou mensagem, dependendo da nomenclatura que deseja usar) chamado “M”.

Interessante isto, não é mesmo? Você notou que para um determinado recurso apareceu diversas notações, nomenclaturas e conceitos? Parece que é para ferrar (para não qualificar com outro adjetivo) com a cabeça do programador.

Dynamic dispatching é um recurso que pode ser muito custoso do ponto de vista de desempenho. Então, antes de usar e abusar, se atente aos requisitos não-funcionais do seu software.

Dentro do universo polimorfismo, existiria alguma coisa nesta linha (de comportamento semelhante) cujo a resolução ocorresse em tempo de compilação e tivesse as garantias da tipagem estática? Com absoluta certeza! Posso garantir que isto existe e formalmente é denominado de Polimorfismo Paramétrico. Isto é refletido diretamente num recurso do C++ chamado templates (e não confunda isto com generics, cujo possuem uma intercecção).

Vamos criar um nome paradoxal para esta brincadeira e chamar tal recurso de static duck typing (olha o pato aparecendo novamente).

Abaixo, uma implementação que remete ao comportamento dos exemplos anteriores com templates e C++:

Internamente, as funções selector e m, serão recriadas pelo compilador, baseado na quantidade de template instantiation.

Ocultamente, o F# também suporta este tal de “static duck typing”. Isto é feito através de inline functions. Estas funções carregam na sua assinatura um contrato formal, por exemplo, (member M : String -> String):

Apesar de ter o mesmo comportamento do C++ template, replicando código com o tipo adequado durante a compilação, você notará 2 coisas que as funções inline fazem:

1. O que um inline supostamente deveria fazer. Substituir a chamada pelas respectivas linhas de código no contexto chamador (linhas L_002f – L_0052).

2. Conserva a estrutura da função inline, mas se chamada dinamicamente gerará uma exceção.

Agora o último ato, o popular, le magnifique, o inconfundível: polimorfismo baseado em hierarquia de classes. Ele mesmo! Aquele que conhecemos através de classes, métodos virtuais e interfaces das linguagens C++, Java, C#, entre outros. Formalmente, este tipo de polimorfismo é denominado de Subtyping Polymorphism.

Aqui vamos explorar apenas 1 modelo: o subtyping polymorphism com dynamic dispatching. Para isto ser possível, em C++, o recurso usado são membros do tipo função virtual. Imagine a seguinte hierarquia e seu consumo:

#include <cstdio>

const float PI = 3.14159265f;

class IConverter
{
public:
    virtual float Convert(float value) = 0;
};

class Radians2Degree : public IConverter
{
public:
    virtual float Convert(float value)
    {
        return 180 * (value / PI);
    }
};

class Degree2Radians : public IConverter
{
public:
    virtual float Convert(float value)
    {
        return PI * (value / 180);
    }
};

int main()
{
    Radians2Degree r2d;
    Degree2Radians d2r;

    IConverter* converter = &r2d;
    std::printf( "2PI in degrees == %f\n", converter->Convert(2 * PI) );

    converter = &d2r;
    std::printf( "360 in radians == %f\n", converter->Convert(360.f) );

    return 0;
}

Você notará que existe uma classe virtual pura (IConverter) servindo de interface base para outras classes. Outros exemplos de tal técnica com interfaces são IUnknown e IInspectable, do COM e da WinRT, respectivamente. Quando existir um membro virtual, existirá a famosa vtable.

A vtable é o mecanismo que possibilita o dynamic dispatching. Sendo que, seu funcionamento é bem simples: imagine um vetor de ponteiros de funções, cujo existe um outro ponteiro (vtable pointer) que referencia esta tabela de funções como membro “privado” ou interno da instância chamadora. Veja este relacionamento na figura abaixo. Toda esta indireção ocorre através do vtable pointer, onde um objeto aciona o ponteiro de função que deseja invocar através de um indice:

No detalhe, em assembly x64, os registradores RCX e RAX mantêem os endereços do objeto (seu this pointer) e do endereço do endereço da função a ser chamada (Convert – 0x000000013F4E68A0). O resultado apresentados estão na forma Little Endian:

Um resumo das principais operações assembly x64 são:

000000013F4E1079  lea         rax,[r2d]
000000013F4E107E  mov         qword ptr [converter],rax
…
000000013F4E1093  mov         rax,qword ptr [converter]
000000013F4E1098  mov         rax,qword ptr [rax]
…
000000013F4E109E  mov         rcx,qword ptr [converter]
000000013F4E10A3  call        qword ptr [rax]  <= breakpoint

RAX    = 0x000000013F4E68A0
RCX    = 0x00000000002CFB38
Memory = 0x000000013F4E68A0  14 10 4e 3f 01 00 00 00 … = littleEndianOf(0x000000013f4e1014)

XMM0 = 00000000000000000000000043B40000 =  resultado final

Apenas por curiosidade, vamos registrar o disassembly do método Convert de Radians2Degree.

A primeira coisa a ser verificada é que para o assembly não existe um método. Há apenas um endereço 64-bit, que poderá ser invocado através do opcode call, cujo a stack indica a presença de 2 paramêtros formais: o this pointer e um float denominado value. Os 2 primeiros passos são movimentos dos registradores onde os parametros foram armazenados antes da chamada para áreas de memória referentes a seus argumentos, o resto das operações são pertinentes aos cálculos. O “S” no final das instruções assembly significa Single, ou seja, operações com float (32-bit ou 4 bytes). Por final, a cópia do resultado vai para o registrador SSE XMM0. Ou seja, simples, muito simples, até “um cavalo entende”.

Dentro do universo amplo do polimorfismo, gostaria de destacar mais 2 modelos:

1. Ad-hoc polymorphism – um nome bonito para sobrecarga de métodos, funções ou operadores.

2. Co-variância e Contra-variância – Conversão do mais específico para o mais genérico e conversão do mais genérico para o mais especifico, respectivamente.

Mas estes são assuntos para uma outra oportunidade, ou para alguma palestra, ou treinamento que eu venha a ser contratado para ministrar.

Samples Polymorphism Source Code

Recursão, recursion, ricorsione, αναδρομή, …

Dentro da Teoria da Computação, um programa pode ser categorizado de acordo com 3 tipos de estruturação: monolítica, iterativa e recursiva.

Fazendo uma analogia com alguma linguagem de programação posso associar a estruturação monolítica ao BASIC que programava quando garoto caracterizado pelo seus desvios incondicionais (vulgo GOTOs e GOSUBs – eu ainda lembro disto, uau!) e estruturação iterativa – populares em linguagens estruturadas, como por exemplo Pascal, e muito forte por banir os desvios incondicionais por serem considerados grosseiros, rídiculos, perigosos, vai dar m… No entanto, isto é teoria, pois na prática todas as (ou a maioria das) linguagens de programação(bem, pelo menos as que eu escolhi para programar) suportam estruturação recursiva, ou seja, suportam recursividade. Alias, isto é um négocio tão simples que “para você entender de recursividade, basta você entender de recursividade”, sacou? Não? Então novamente: “para você entender de recursividade, basta você entender de recursividade” – agora sim!

Baseado num famoso trecho de Orwell, posso dizer: “… que algumas linguagens são mais recursivas do que outras”.

A maioria dos programadores que conheço sabem ou já ouviram falar sobre recursividade. Mas se você perguntar o que é, provavelmente a resposta seria: “Ah, é uma função que chama a si própria”. Ok! Este é um tipo: a função recursiva. O outro é a estrutura de dados recursiva: o nó de uma lista ligada (Linked List) ou de uma árvore (Tree), a enumeração de dirétorios e arquivos ou de janelas.

Recursividade é tão importante que é um dos pilares das Linguagens Funcionais e um recurso fundamental para a Matemática. Por exemplo, o algoritmo babilônico para a computação do lado do quadrado (square root) é definido recursivamente por:

O “sr” na função representa um chute (guess), você calculará inúmeras (“n”) vezes até chegar num resultado coerente dentro de “k” casas decimais para o valor de “x” – você perceberá que esta coerência surgirá quando uma execução sucessiva produzirá resultados semelhantes ou muito, mas muito, próximos. Let’s try:

Note que no Mathematica, o algoritmo está um pouco modificado em relação ao apresentado.

Interessante isto, não é mesmo? Tão interessante quanto, é saber que é possível representar estruturas de controle, tais como for ou while, em termos recursivos.

No exemplo, escrito em Scala, a função recursiva While é uma função tail recursive. Resumidamente, isto significa que o compilador ou máquina virtual (ou ambos) conseguem otimizar a chamada e não sobrecarregar a call stack.

Imagine por um momento, que surgisse uma vontade incontrolável de implementar um código para gerar séries harmonicas em C++. E falaram para você que este tal de C++ suporta Orientação a Objetos. Juntamente com esta vontade te consumindo, você também ouviu falar num cara chamado Template Method Pattern. Decidido a misturar tudo isto e ver o que pode dar, escreveu o seguinte código, que por sinal usa chamadas recursivas e é compilado com a máaaaaaxima otimização possível:

Apesar de eu não ter te explicado, você percebeu que o método SummationCore da classe Harmonic é implementado totalmente segundo os principios de comandam uma boa função tail recursive. O problema é que você caiu numa armadilha do C++.

O fato é: o método é virtual, ele necessita ser resolvido em tempo de execução, então o C++ (pelo menos o cl.exe [Microsoft (R) C/C++ Optimizing Compiler Version 16.00.40219.01], digo o compilador do Visual C++ 10) não pode otimizar agressivamente este código. Note a quantidade de chamadas na Call Stack!

Para concertar este problema, sem alterar a estrutura do código ou usar templates, como regra básica assuma: toda vez que um método virtual for resolvido como tail recursive, implemente-o em termos de outro método não virtual. Assim, o compilador poderá produzir um resultado otimizado! (E este resultado é exatamente resolvido através de desvios – JMPs ou GOTOs, mas esta é uma outra estória)

A versão tail recursive em C++, na integra:

#include <cstdio>

struct Serie
{
    virtual ~Serie(){}

    float Summation(int n)
    {
        return SummationCore(n);
    }

protected:
    virtual float SummationCore(int n) = 0;
};

struct Harmonic : public Serie
{
    Harmonic() : Acc_(0){}

protected:
    virtual float SummationCore(int n)
    {
        return TailRecursiveSummation(n);
    }

    float TailRecursiveSummation(int n)
    {
        if(n == 1)
            return Acc_;

        Acc_ += 1.0 / n;

        return TailRecursiveSummation(n - 1);
    }

private:
    float Acc_;
};

int main()
{
    std::printf( "%f", Harmonic().Summation(7) );
}

Não esqueça de olhar a Call Stack (impressionante, não acha?)

Replanejamento do Blog – 2012 Comeback Special

Estou replanejando o meu blog sobre Programação de Software. Desta vez será escrito na maior parte em português. Em breve, este post dará lugar para outros mais interessantes…