A concurrent program is one in which a number of processes are considered to be active simultaneously . It is possib l e to t hink of a process as being a separate sequential program executing independently of other processes, although perhaps communicating with them at desired pOints . The concurrent program, as a whole, can be executed in one of two ways: il ii) in true concurrent manner, wi th each process executing on a dedicated processor in a quasi - concurrent manner, where a processor's processes . time is multiplexed between single the There are two motivations for the study of concurrency in programming languages : i) concurrent programming facilities can be exploited in systems where one has more t han one processor . As technology i mproves, machines having multiple processors will proliferate ii) concurrent p r ogramming facilities may allow programs to be structured as independent , bu t co - operating, processes which can then be implemented on a single processor system . This structure may be more natural to the programmer then the traditional sequential structures. An example is provided by Conway's - 1- Clearly, languages Pascal) problem [Ben82] . by their very nature, traditional sequential- type (Fortran, Basic, Cobol and earlier versions of prove inadequate for the purposes of concurrent programming without considerable extension (which some manufacturers have provided, rendering their compilers non standard-conforming). The general convenience of high level languages provides strong motivation for their development for rea l time programming. Modula - 2 [Wir83] is but one of a number of such r ecently developed languages, designed not only to fulfil a "sequential" role but also to offer facilities for concurrent programming. Developed by Niklaus Wirth in 1979 as a successor to Pascal and Modula, it is intended to serve under the banner of a generalpurpose systems - implementation language. This thesis investigates concurrency i n Modula - 2 and takes the following form: i ) an analYSis of the concurrent facilities offered ii) problems and difficulties associated with these facilities iii) improveme nts and enhancements, including the feasibility of using Modula - 2 to simulate constructs found in other languages, such as the Hoare monitor [Hoa74] and the Ada rendezvous [Uni81]. - 2- Each section concludes with an appraisal of the work conducted in that section . The final section consists of a critical assessment of those Modula - 2 language constructs and facilities provided for the implementation of concurrency and a brief look at concurrency in Modula, Modula-2's predecessor. - Introduction. / KMBT_363 / Adobe Acrobat 9.53 Paper Capture Plug-in

Computaçãao quântica pode ser entendida como transformação da informação codificada no estado de um sistema físico quântico. A idéia básica da computação quântica é codificar dados utilizando bits quânticos (qubits). Diferentemente do bit clássico, o qubit pode existir em uma superposição dos seus estados básicos permitindo o “paralelismo quântico”, o qual é uma característica importante da computação quântica visto que pode aumentar consideravelmente a velocidade de processamento dos algoritmos. Entretanto, tipos de dados quânticos são bastante poderosos não somente por causa da superposição de estados. Existem outras propriedades ímpares como medida e emaranhamento. Nesta tese, nós discutimos que um modelo realístico para computações quânticas deve ser geral com respeito a medidas, e completo com respeito a comunicação entre o mundo quântico e o mundo clássico. Nós, então, explicamos e estruturamos computações quânticas gerais e completas em Haskell utilizando construções conhecidas da área de semântica e linguagens de programação clássicas, como mônadas e setas. Em mais detalhes, esta tese se concentra nas seguintes contribuições. Mônadas e Setas. Paralelismo quântico, emaranhamento e medida quântica certamente vão além do escopo de linguagens funcionais “puras”. Nós mostramos que o paralelismo quântico pode ser modelado utilizando-se uma pequena generalização de mônadas, chamada mônadas indexadas ou estruturas Kleisli. Além disso, nós mostramos que a medida quântica pode ser explicada utilizando-se uma generalização mais radical de mônadas, as assim chamadas setas, mais especificamente, setas indexadas, as quais definimos nesta tese. Este resultado conecta características quânticas “genéricas” e “completas” `a construções semânticas de linguagens de programação bem fundamentadas. Entendendo as Interpretações da Mecânica Quântica como Efeitos Computacionais. Em um experimento hipotético, Einstein, Podolsky e Rosen demonstraram algumas consequências contra-intuitivas da mecânica quântica. A idéia básica é que duas partículas parecem sempre comunicar alguma informação mesmo estando separadas por uma distância arbitrariamente grande. Existe muito debate e muitos artigos sobre esse tópico, mas é interessante notar que, como proposto por Amr Sabry, essas características estranhas podem ser essencialmente modeladas por atribuições a variáveis globais. Baseados nesta idéia nós modelamos este comportamento estranho utilizando noções gerais de efeitos computacionais incorporados nas noções de mônadas e setas. Provando Propriedades de Programas Quânticos Utilizando Leis Algébricas. Nós desenvolvemos um trabalho preliminar para fazer provas equacionais sobre algoritmos quânticos escritos em uma sublinguagem pura de uma linguagem de programação funcional quântica, chamada QML. / Quantum computation can be understood as transformation of information encoded in the state of a quantum physical system. The basic idea behind quantum computation is to encode data using quantum bits (qubits). Differently from the classical bit, the qubit can be in a superposition of basic states leading to “quantum parallelism”, which is an important characteristic of quantum computation since it can greatly increase the speed processing of algorithms. However, quantum data types are computationally very powerful not only due to superposition. There are other odd properties like measurement and entangled. In this thesis we argue that a realistic model for quantum computations should be general with respect to measurements, and complete with respect to the information flow between the quantum and classical worlds. We thus explain and structure general and complete quantum programming in Haskell using well known constructions from classical semantics and programming languages, like monads and arrows. In more detail, this thesis focuses on the following contributions. Monads and Arrows. Quantum parallelism, entanglement, and measurement certainly go beyond “pure” functional programming. We have shown that quantum parallelism can be modelled using a slightly generalisation of monads called indexed monads, or Kleisli structures. We have also build on this insight and showed that quantum measurement can be explained using a more radical generalisation of monads, the so-called arrows, more specifically, indexed arrows, which we define in this thesis. This result connects “generic” and “complete” quantum features to well-founded semantics constructions and programming languages. Understanding of Interpretations of QuantumMechanics as Computational Effects. In a thought experiment, Einsten, Podolsky, and Rosen demonstrate some counter-intuitive consequences of quantum mechanics. The basic idea is that two entangled particles appear to always communicate some information even when they are separated by arbitrarily large distances. There has been endless debate and papers on this topic, but it is interesting that, as proposed by Amr Sabry, this strangeness can be essentially modelled by assignments to global variables. We build on that, and model this strangeness using the general notions of computational effects embodied in monads and arrows. Reasoning about Quantum Programs Using Algebraic Laws. We have developed a preliminary work to do equational reasoning about quantum algorithms written in a pure sublanguage of a functional quantum programming language, called QML.

Neste trabalho é descrita a organização de SINSEM, um sistema de processamento automático de especificação SINtático-SEMânticas de linguagens de programação. É colocada a motivação para um tal sistema, em relação ao uso que se daria a ele. O sistema é situado entre sistemas similares, dos quais alguns são brevemente descritos, incluindo-se exemplos de uso. Procura-se estabelecer conceitos relativos as trabalho com sistemas de auxilio ao projeto e à implementação de linguagens de programação. É discutida a estrutura lógica do sistema e uma filosofia de utilização, bem como é apresentada a nova metalinguagem proposta construído a partir da notação BNF, com extensões para se exprimir a semântica de uma linguagem de um modo construtivo, permitindo a especificação de gramáticas livres do contexto sem recursões a esquerda, visando a produção de reconhecedores recursivos descendentes dotados de ações semânticas. São apresentadas a sintaxe concreta e estática da metalinguagem, explicando-se também as funções semânticas (do tipo estático e do tipo concreto) pré-definidas no ambiente de desenvolvimento onde a ferramenta se integra. Tal ambiente pode ser operado por um conjunto de comandos que constituem uma interface (o "envelope"), que inclui também uma biblioteca sintático-semântica (que pode ser atualizada pelo usuário). A interface é descrita por meio de DFD'S E DE UM DICIONÁRIO DE DADOS. Ao final é apresentado um exemplo, parcialmente comentado (capítulo 5), de definição completa de uma linguagem de programação (CSSD), usando-se a metalinguagem proposta e os itens pré-definidos da biblioteca sintático-semântica. / In this work it is specified the constitution of SINSEM, an automatic processing system for SYNtactic and SEMantic specifications of programming languages. it is discussed motivation for such a system, according to uses it could have. The system is situated among similar systems, and some of these are briefly described, including examples. It is attempted to establish concepts about working with ,design and implementation aiding systems for programming languages. It is discussed the logical structure of the system and a philosophy of use, as well is presented a new metalanguage proposal for syntactic and semantic descriptions that is a production system constructed from BNF notation, with extensions to give language semantics in a constructive way, allowing specification of free context grammars with no left recursions, aiming the generation of preliminary versions of recursive descent parsers with semantic actions. The abstract and concrete syntax of the metalanguage are presented, and are also explained the semantic functions (of static and concrete type) predefined with and within the development environment where this frame is inserted. That environment can be operated by a set of commands that constitutes an interface ( the " envelope") wich includes too a syntactic-semantic library ( this can be made up to date by the user own). The interface is described by means of a set of DFD's and a data dictionary. At the end. it is presented an example, partially commented (chapter 5), of a complete definition of a programming language ( CSSD ), using the proposed metalanguage and the predefined items of the syntactic-semantic iibrary.

abstract: Graph theory is a critical component of computer science and software engineering, with algorithms concerning graph traversal and comprehension powering much of the largest problems in both industry and research. Engineers and researchers often have an accurate view of their target graph, however they struggle to implement a correct, and efficient, search over that graph. To facilitate rapid, correct, efficient, and intuitive development of graph based solutions we propose a new programming language construct - the search statement. Given a supra-root node, a procedure which determines the children of a given parent node, and optional definitions of the fail-fast acceptance or rejection of a solution, the search statement can conduct a search over any graph or network. Structurally, this statement is modelled after the common switch statement and is put into a largely imperative/procedural context to allow for immediate and intuitive development by most programmers. The Go programming language has been used as a foundation and proof-of-concept of the search statement. A Go compiler is provided which implements this construct. / Dissertation/Thesis / Masters Thesis Software Engineering 2018

Domain-specific, “little” languages are commonplace in computing. So too is the need to implement such languages; to meet this need, we have created SPARK (Scanning, Parsing, And Rewriting Kit), a toolkit for little language implementation in Python, an object-oriented scripting language. SPARK greatly simplifies the task of little language implementation. It requires little code to be written, and accommodates a wide range of users—even those without a background in compiler theory. Our toolkit is seeing increasing use on a variety of diverse projects. SPARK was designed to be easy-to-use with few limitations, and relies heavily on Earley's general parsing algorithm internally, which helps in meeting these design goals. Earley's algorithm, in its standard form, can be hard to use; indeed, experience with SPARK has highlighted several problems with the practical use of Earley's algorithm. Our research addresses and provides solutions for these problems, making some significant improvements to the implementation and use of Earley's algorithm. First, Earley's algorithm suffers from the performance problem . Even under optimum conditions, a standard Earley parser is burdened with overhead. We extend directly-executable parsing techniques for use in Earley parsers, the results of which run in time comparable to the much-more-specialized LALR(1) parsing algorithm. Second is what we call the delayed action problem. General parsers like Earley must, in the worst case, read the entire input before executing any semantic actions associated with the grammar rules. We attack this problem in two ways. We have identified conditions under which it is safe to execute semantic actions on the fly during recognition; as a side effect, this has yielded space savings of over 90% for some grammars. The other approach to the delayed action problem deals with the difficulty of handling context-dependent tokens. Such tokens are easy to handle using what we call “Schrödinger's tokens,” a superposition of token types. Finally, Earley parsers are complicated by the need to process grammar rules with empty right-hand sides. We present a simple, efficient way to handle these empty rules, and prove that our new method is correct. We also show how our method may be used to create a new type of LR(0) automaton which is ideally suited for use in Earley parsers. Our work has made Earley parsing faster and more space-efficient, turning it into an excellent candidate for practical use in many applications. / Graduate

Des sémantiques élégantes et des implémentations efficaces des langages de programmation fonctionnels peuvent être décrits par les mêmes structures mathématiques, notamment dans la correspondance Curry-Howard, où le programmes, les types et l’exécution, coïncident aux preuves, formules et normalisation. Une telle flexibilité est aiguisé par l’approche déconstructive et géométrique de la logique linéaire (LL) et les réseaux de preuve, et de la réduction optimale et les graphes de partage (SG).En adaptent la géométrie de l’interaction de Girard, cette thèse propose une géométrie de l’interaction des ressources (GoRI), une sémantique dynamique et dénotationnelle, qui décrit algébriquement par leurs chemins, les termes du calcul des ressources (RC), une variation linéaire et non-déterministe du lambda calcul (LC). Les séries infinis dans RC sont aussi le domaine du développement de Taylor-Ehrhard-Regnier, une linéarisation du LC. La thèse explique la relation entre ce dernier et la réduction démontrant qu’ils commutent, et présente une version développé de la formule d’exécution pour calculer les chemins du LC typé.Les SG sont un modèle d’implémentation du LC, dont les pas sont locales et asynchrones, et le partage implique et les termes et les contextes. Bien que les tests ont montré des accélérations exceptionnelles, jusqu à exponentielles, par rapport aux implémentations traditionnelles, les SG n’ont pas que des avantages. La thèse montre que, dans le cas restreint des réseaux élémentaires, où seule le cœur des SG est requis, les désavantages sont au plus quadratique, donc inoffensifs. / Elegant semantics and efficient implementations of functional programming languages can both be described by the very same mathematical structures, most prominently with in the Curry-Howard correspondence, where programs, types and execution respectively coincide with proofs, formulæ and normalisation. Such a flexibility is sharpened by the deconstructive and geometrical approach pioneered by linear logic (LL) and proof-nets, and by Lévy-optimal reduction and sharing graphs (SG).Adapting Girard’s geometry of interaction, this thesis introduces the geometry of resource interaction (GoRI), a dynamic and denotational semantics, which describes, algebra-ically by their paths, terms of the resource calculus (RC), a linear and non-deterministic variation of the ordinary lambda calculus. Infinite series of RC-terms are also the domain of the Taylor-Ehrhard-Regnier expansion, a linearisation of LC. The thesis explains the relation between the former and the reduction by proving that they commute, and provides an expanded version of the execution formula to compute paths for the typed LC. SG are an abstract implementation of LC and proof-nets whose steps are local and asynchronous, and sharing involves both terms and contexts. Whilst experimental tests on SG show outstanding speedups, up to exponential, with respect to traditional implementations, sharing comes at price. The thesis proves that, in the restricted case of elementary proof-nets, where only the core of SG is needed, such a price is at most quadratic, hence harmless. / Semantiche eleganti ed implementazioni efficienti di linguaggi di programmazione funzionale possono entrambe essere descritte dalle stesse strutture matematiche, più notevolmente nella corrispondenza Curry-Howard, dove i programmi, i tipi e l’esecuzione coincidono, nell’ordine, con le dimostrazioni, le formule e la normalizzazione. Tale flsesibilità è acuita dall’approccio decostruttivo e geometrico della logica lineare (LL) e le reti di dimostrazione, e della riduzione ottimale e i grafi di condivisione (SG).Adattando la geometria dell’interazione di Girard, questa tesi introduce la geometria dell’interazione delle risorse (GoRI), una semantica dinamica e denotazionale che descrive, algebricamente tramite i loro per-corsi, i termini del calcolo delle risorse (RC), una variante lineare e non-deterministica del lambda calcolo ordinario. Le serie infinite di termini del RC sono inoltre il dominio dell’espansione di Taylor-Ehrhard-Regnier, una linearizzazione del LC. La tesi spiega la relazione tra quest’ultima e la riduzione dimostrando che esse commutano, e fornisce una versione espansa della for-mula di esecuzione per calcolare i percorsi del LC tipato. I SG sono un modello d’implementazione del LC, i cui passi sono loc-ali e asincroni, e la cui condivisione riguarda sia termini che contesti. Sebbene le prove sperimentali sui SG mostrino accellerazioni eccezionali, persino esponenziali, rispetto alle implementazioni tradizionali, la condivisione ha un costo. La tesi dimostra che, nel caso ristretto delle reti elementari, dove è necessario solo il cuore dei SG, tale costo è al più quad-ratico, e quindi innocuo.

A Computação Pervasiva tem sido tema de diversos trabalhos nos últimos anos. Essa emergente área de pesquisa propõe uma visão de futuro onde serviços computacionais são oferecidos para os usuários através de inúmeros dispositivos espalhados pelo ambiente. Os serviços são disponibilizados, tanto através da infraestrutura existente dos computadores ligados fisicamente à rede quanto através de dispositivos móveis. Esse espalhamento da computação deve acontecer de maneira natural e imperceptível ao usuário. Dados pessoais, programas e arquivos de dados poderão ser acessados de qualquer lugar em qualquer momento. O poder de processamento será um recurso do ambiente, acessado quando necessário, da mesma forma que é hoje a eletricidade. O usuário não precisará ter ciência de qual máquina realiza o processamento necessário às suas aplicações, contanto que o resultado esperado seja obtido. Acredita-se que essa realidade será atingida através da aliança entre áreas de pesquisa como a Computação em Grade, Computação Móvel e a Computação Consciente do Contexto. A Computação Consciente do Contexto busca enriquecer a comunicação entre os seres humanos e os dispositivos computacionais, tornando sua atuação mais eficaz. As aplicações conscientes do contexto conseguem perceber as modificações que ocorrem no ambiente e adaptar seu comportamento ao novo estado. Esse processo pode ser dividido em três etapas: monitoramento, reconhecimento de contexto e adaptação. Na etapa de monitoramento são coletadas, através de sensores, informações sobre o ambiente. Essas informações, entretanto, são geralmente, de baixo nível de abstração e, portanto, dificilmente usadas diretamente por aplicações. A etapa de reconhecimento de contexto relaciona os dados obtidos do ambiente e transforma-os para que possam ser úteis às aplicações no processo de escolha do comportamento mais adequado à cada circunstância, habilitando a etapa de adaptação a efetivar a transformação do comportamento da aplicação de acordo com a nova situação do ambiente. Este trabalho propõe um servidor de contexto chamado MultiS que tem como objetivo a resolução dos problemas relativos à etapa de reconhecimento de contexto: a produção de dado de contexto baseado em informações de diversos sensores e a capacidade de reagir a modificações no ambiente. Também é proposta uma linguagem para composição de dados do contexto chamada CD-XML utilizada pelas aplicações para descrever ao servidor de contexto os dados aos quais elas são sensíveis. / The Pervasive Computing has been studied on several papers in the last years. This emergent research area presents a vision of future where computational services will be available through uncountable devices scattered across the environment. This service network will be exposed to the users by both traditional wired computers and mobile devices. This distribution of the computing is going to happen smoothly and transparently to the users. Personal data, computer programs, and data files will be available anywhere, anytime. The processing power will be an environment resource and will be accessed whenever needed, in the same way which is the electricity nowadays. The users will no longer need to worry about where their program is being executed, as long as he gets the needed result. The ISAM group believes that this new reality will be achieved through the alliance of research areas such as Grid Computing, Mobile Computing and Context-Aware Computing. The Context-Aware Computing aims to enrich the communication between human being and computer devices. Context-aware applications are capable of recognize the changes on the environment and adapt its own behavior to the new context state. This process can be divided in tree steps: monitoring, context recognition and adaptation. On the monitoring layer, environment information is collected from sensors. Those sensors, however, usually return only low level information, which is hardly used by the applications on its original form. The context recognition layer processes the data acquired from the context and transforms into information aimed to be useful to the adaptation process. With that information the adaptation system can identify the correct behavior for the application on each different context situation. This dissertation propose a context server named MultiS, which target is to solve the problems related to context recognition layer: the production of new context data based on the information of several sensors and the capability of react to changes on the environment. It also presents a new programming language for composition of contextual information, named CD-XML. This language is used by the context-aware applications to communicate to the context server describing which information the application is sensible to.

NestStep is a collection of parallel extensions to existing programming languages. These extensions supports a shared memory model and nested parallelism. NestStep is based the Bulk-Synchronous Programming model. Most of the communication of data in NestStep takes place in a combine/commit phase, which is essentially a reduction followed by a broadcast. The primary aim of the project that this thesis is based on was to develop a runtime system for NestStep-C, the extensions for the C programming language. The secondary aim was to find which tree structure among a selected few is the best for communicating data in the combine/commit phase. This thesis includes information about NestStep, how to interface with the NestStep runtime system, some example applications and benchmarks for determining the best tree structure. A binomial tree structure and trees similar to it was empirically found to yield the best performance.

Este trabalho apresenta uma proposta para implementação de um subconjunto de instruções e comandos de uma linguagem Pascal Padrão ISSO, aplicada a arquitetura RISC, tendo como base a arquitetura RISC-LIE [Vale91], proposta e desenvolvida no IFQSC. Para definição e construção de parte do código gerado foi utilizada a ferramenta de desenvolvimento de compiladores YACC, que definiu toda estrutura gramatical da linguagem, sendo que as demais estruturas foram desenvolvidas usando interfaces em linguagem C. O código gerado pelo computador utilizou trinta instruções de máquina que compõe o simulador da arquitetura RISC-LIE, gerando assim códigos compatíveis que podem ser interpretados por esse simulador. / This work presents a proposal for an implementation of a subset of instructions and commands of Standard Pascal ISO applied to RISC architectures. The work was developed using the RISC-LIE architecture as our target [Vale91]. The RISC-LIE has been proposed and developed at IFQSC. Part of the code was defined and constructed using YACC, a tool for compilers development which defined the grammatical structure of language. The remainder routines were developed using the C language. The code produced by the compiler used the thirty instructions of the RISC-LIE instruction set. These instructions are implemented in the RISC-LIE architecture simulator. Therefore, generates codes that can be interpreted by this simulator.

Neste trabalho é descrita a organização de SINSEM, um sistema de processamento automático de especificação SINtático-SEMânticas de linguagens de programação. É colocada a motivação para um tal sistema, em relação ao uso que se daria a ele. O sistema é situado entre sistemas similares, dos quais alguns são brevemente descritos, incluindo-se exemplos de uso. Procura-se estabelecer conceitos relativos as trabalho com sistemas de auxilio ao projeto e à implementação de linguagens de programação. É discutida a estrutura lógica do sistema e uma filosofia de utilização, bem como é apresentada a nova metalinguagem proposta construído a partir da notação BNF, com extensões para se exprimir a semântica de uma linguagem de um modo construtivo, permitindo a especificação de gramáticas livres do contexto sem recursões a esquerda, visando a produção de reconhecedores recursivos descendentes dotados de ações semânticas. São apresentadas a sintaxe concreta e estática da metalinguagem, explicando-se também as funções semânticas (do tipo estático e do tipo concreto) pré-definidas no ambiente de desenvolvimento onde a ferramenta se integra. Tal ambiente pode ser operado por um conjunto de comandos que constituem uma interface (o "envelope"), que inclui também uma biblioteca sintático-semântica (que pode ser atualizada pelo usuário). A interface é descrita por meio de DFD'S E DE UM DICIONÁRIO DE DADOS. Ao final é apresentado um exemplo, parcialmente comentado (capítulo 5), de definição completa de uma linguagem de programação (CSSD), usando-se a metalinguagem proposta e os itens pré-definidos da biblioteca sintático-semântica. / In this work it is specified the constitution of SINSEM, an automatic processing system for SYNtactic and SEMantic specifications of programming languages. it is discussed motivation for such a system, according to uses it could have. The system is situated among similar systems, and some of these are briefly described, including examples. It is attempted to establish concepts about working with ,design and implementation aiding systems for programming languages. It is discussed the logical structure of the system and a philosophy of use, as well is presented a new metalanguage proposal for syntactic and semantic descriptions that is a production system constructed from BNF notation, with extensions to give language semantics in a constructive way, allowing specification of free context grammars with no left recursions, aiming the generation of preliminary versions of recursive descent parsers with semantic actions. The abstract and concrete syntax of the metalanguage are presented, and are also explained the semantic functions (of static and concrete type) predefined with and within the development environment where this frame is inserted. That environment can be operated by a set of commands that constitutes an interface ( the " envelope") wich includes too a syntactic-semantic library ( this can be made up to date by the user own). The interface is described by means of a set of DFD's and a data dictionary. At the end. it is presented an example, partially commented (chapter 5), of a complete definition of a programming language ( CSSD ), using the proposed metalanguage and the predefined items of the syntactic-semantic iibrary.