Universitätspublikationen
Refine
Year of publication
- 2007 (5) (remove)
Document Type
- Working Paper (5) (remove)
Language
- English (5) (remove)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Keywords
- Lambda-Kalkül (1)
- Programmtransformation (1)
- call-by-name (1)
- call-by-need (1)
- context lemma (1)
- functional programming languages (1)
- infinitary lambda calculus (1)
- lambda calculus (1)
- lambda-calculus (1)
- lazy evaluation (1)
Institute
This paper proves several generic variants of context lemmas and thus contributes to improving the tools to develop observational semantics that is based on a reduction semantics for a language. The context lemmas are provided for may- as well as two variants of mustconvergence and a wide class of extended lambda calculi, which satisfy certain abstract conditions. The calculi must have a form of node sharing, e.g. plain beta reduction is not permitted. There are two variants, weakly sharing calculi, where the beta-reduction is only permitted for arguments that are variables, and strongly sharing calculi, which roughly correspond to call-by-need calculi, where beta-reduction is completely replaced by a sharing variant. The calculi must obey three abstract assumptions, which are in general easily recognizable given the syntax and the reduction rules. The generic context lemmas have as instances several context lemmas already proved in the literature for specific lambda calculi with sharing. The scope of the generic context lemmas comprises not only call-by-need calculi, but also call-by-value calculi with a form of built-in sharing. Investigations in other, new variants of extended lambda-calculi with sharing, where the language or the reduction rules and/or strategy varies, will be simplified by our result, since specific context lemmas are immediately derivable from the generic context lemma, provided our abstract conditions are met.
We develop a proof method to show that in a (deterministic) lambda calculus with letrec and equipped with contextual equivalence the call-by-name and the call-by-need evaluation are equivalent, and also that the unrestricted copy-operation is correct. Given a let-binding x = t, the copy-operation replaces an occurrence of the variable x by the expression t, regardless of the form of t. This gives an answer to unresolved problems in several papers, it adds a strong method to the tool set for reasoning about contextual equivalence in higher-order calculi with letrec, and it enables a class of transformations that can be used as optimizations. The method can be used in different kind of lambda calculi with cyclic sharing. Probably it can also be used in non-deterministic lambda calculi if the variable x is “deterministic”, i.e., has no interference with non-deterministic executions. The main technical idea is to use a restricted variant of the infinitary lambda-calculus, whose objects are the expressions that are unrolled w.r.t. let, to define the infinite developments as a reduction calculus on the infinite trees and showing a standardization theorem.
The goal of this report is to prove correctness of a considerable subset of transformations w.r.t. contextual equivalence in an extended lambda-calculus LS with case, constructors, seq, let, and choice, with a simple set of reduction rules; and to argue that an approximation calculus LA is equivalent to LS w.r.t. the contextual preorder, which enables the proof tool of simulation. Unfortunately, a direct proof appears to be impossible.
The correctness proof is by defining another calculus L comprising the complex variants of copy, case-reduction and seq-reductions that use variable-binding chains. This complex calculus has well-behaved diagrams and allows a proof of correctness of transformations, and that the simple calculus LS, the calculus L, and the calculus LA all have an equivalent contextual preorder.
Namibia is known to be the most arid country south of the Sahara. Average annual rainfall is not only relatively low in most parts of the country, it is also highly variable. Only 8 per cent of the country receives enough rain during a normal rainy season to practice rainfed cultivation. At the same time between 60 per cent and 70 per cent of the population depend on subsistence agro-pastoralism in non-freehold or communal areas. Against the background of rising unemployment, the livelihoods of the majority of these people are likely to depend on natural resources in the foreseeable future.
Natural resources generally are under considerable strain. As the rural population increases, so is the demand for natural resources, land and water specifically. Dependency on subsistence farming which is the result of large scale rural poverty exacerbates the problem. Large parts of the country are stocked injudiciously, resulting in overgrazing and water is frequently overabstracted, leading to declining water tables (MET 2005: 2).
Unequal access to both land and water has prompted government to introduce reforms in these sectors. These reforms were guided by the desire to manage resources more sustainably while providing more equal access to them. In terms of NDP 2, sustainability means to use natural resources in such a way so as not to ‘compromise the ability of future generations to make use of these resources’ (NDP 2: 595).
Immediately after Independence government started reform processes in the land and water sectors. However, these reforms have happened at different paces and largely independent of each other. Increasingly policy makers and development practitioners realised that land and water management needed to be integrated, as decisions about land management and land use options had a direct impact on water resources. Conversely the availability of water sets the parameters for what is possible in terms of agricultural production and other land uses. The north-central regions face a particular challenge in this regard as the region carries more livestock than it can sustain in the long run. At the same time, close to half the households do not own any livestock. Access to livestock by these households would improve their abilities to cultivate their land more efficiently in order to feed themselves and thus reduce poverty levels.
But livestock are a major consumer of water. In 2000 livestock was consuming more water than the domestic sector. The figures were 77Mm3/a and 67Mm3/a respectively (Urban et al. 2003 Annex 7: 2). This situation has prompted a Project Progress Report on the Namibia Water Resources Management Review in 2003 to conclude that Given the extreme water scarcity in most parts of the country, land and water issues are closely linked. It therefore seems indispensable to mutually adjust land – and water sector reform processes (Ibid: 20).
This paper will briefly look at four institutions that are central to land and water management with a view to assess the extent to which they interact. These are Communal Land Boards, Water Point Committees, Traditional Authorities and Regional Councils. A discussion of relevant policy documents and legislative instruments will investigate whether the existing policy framework
provides for an integrated approach or not. Before doing this, it appears sensible to briefly situate these four institutions in the wider maze of institutions operating at regional and
sub-regional level. All these institutions – important as they are in the quest to improve participation at the regional and sub-regional level – are competing for time and input fros mallscale farmers.