paperclips please

The following is a paper I wrote for a graduate networking class at the University of Melbourne. A link to the properly formatted pdf is available here. The title “Geographic Routing in VANETs” was inherited from the brief, I however choose to focus my discussion on a very specific area of interest. This work received 93% and was graded at a graduate coursework standard in the Faculty of Engineering.

In Vehicular Ad-hoc Networks (VANETs) maintaining reliable communication is a challenge due to the high mobility of vehicles, frequent topology changes and intermittent connectivity. Traditional routing protocols assume stable and continuous connections and struggle in dynamic environments. Since geographic information is of relevance to fast moving vehicles, routing based on geographic location has become popular means by which route orientations can be determined. Vehicles manage their own location data and the locations of neighbouring vehicles with the aid GPS to make informed routing decisions about next hop rather than making use of tradition routing tables[1]. This approach creates many opportunities for constraint optimisation since most geographic-based protocols employ a heuristic.

Vehicular Delay/Disruption Tolerant Networks (VDTNs) are a specialised form of Delay Tol- erant Networks (DTNs) designed to address the challenges peculiar to VANETs [2]. VDTN represents a special case of VANET research. VDTNs tolerate delays and disruptions in network connectivity by utilizing store-carry-forward mechanisms. Data packets are stored temporarily in a vehicle’s memory and carried until a connection can be established with the next node[3][4]. This approach ensures that messages eventually reach their destination even if an end-to-end path does not exist at all times. In order to understand the VDTN category within VANETs, a brief history of the routing failures in this space is rehearsed in this section. There are two main category schemes for VANETs. The first scheme separates based on the nature of the routingprotocol across categories: ad hoc, cluster-based, broadcast, geocast and geography-based [5] [6]. Within geographic routing there is a focus on delay tolerant networks with a putative correspondence of consumer needs over a beacon-less Vehicle-to-Vehicle environment [7]. The following will address the ontology of VDTN.
VANETs are decentralized networks that function independently of traditional networking infrastructure, with connections routed hop-by-hop, where users act as custodians of messages en route. This presents unique challenges compared to other networking protocols. Despite efforts to develop specific VANET routing protocols, the first generation of these protocols carried major assumptions from IP-based networks, implementing a store-and-forward approach. They assumed that a route could generally be found from a source to a destination if a delay was acceptable. Consequently, these protocols struggled with long disruptions and suffered significant efficiency losses as delays increased[1]. They failed to handle the extreme networking conditions common in vehicular networking.
DTN – To address the shortcomings, DTNs were applied to VANETs. DTNs are used in con- texts where intermittent connectivity is commonplace, such as interplanetary communications, and networking conditions where frequent and prolonged periods of disconnection between nodes is a consistent possibility[1]. This concern necessitates protocols that can adapt to rapid changes in network structure. Along with these constraints, nodes in DTNs often face resource constraints, including limited power and storage capacities, which demand energy-efficient and storage-efficient communication strategies. DTNs also often have high mobility, resulting in a highly dynamic network topology and variable node density, which is a putative concern in vehicular networking. They tolerate high latency, accommodating significant delays in data de- livery, making them suitable for delay-insensitive applications where immediate communication is not critical. The network’s heterogeneity further complicates the scenario, as DTNs often comprise diverse devices with varying capabilities, requiring interoperability and communication support across different types of nodes. Finally, Opportunistic communication is a common case of DTNs, where data transfer occurs opportunistically as nodes come into contact with each other. This necessitates adaptive routing decisions based on current network conditions and node availability. To handle frequent disruptions and ensure data delivery despite network fragmentation, DTNs employ robust protocols, redundancy, and replication techniques [3].
Store-Carry-and-Forward – (SCF) To address these problems, an SCF mechanism is im- plemented where nodes store data packets until a communication opportunity arises and then forward them to the next hop or destination [3]. Contrasting significantly with the store-and- forward operation used in Internet routing a DTN node can store a bundle permanently and carry it until a suitable forwarding opportunity arises. This allows data to be held and transported over long periods and distances until the node encounters another suitable node to relay the bundle.
The Bundle Protocol – In [4] the DTN Research Group (DTNRG) proposed an architecture and the Bundle Protocol for DTNs. A message-oriented overlay layer called the “Bundle Layer” is added above the particular layer(s) of the networks it interconnects. The Bundle Layer transforms application data units into protocol data units called “bundles,” which are then forwarded by DTN nodes according to the Bundle Protocol [8]. These bundles contain all the information needed by the destination to complete a transaction in one go, including protocol and authentication data, which is crucial since multiple round trips between nodes may not be feasible. The protocol allows bundles to be stored permanently and forwarded in a hop-by-hop scheme, rather than end-to-end, whenever a new transmission opportunity arises—such as when two DTN nodes come into contact. Notably, the protocol does not provide error detection or correction capabilities, which must be managed by upper layers[4]. This approach minimizes the number of round-trip exchanges by bundling all necessary transaction information, which benefits environments with large round-trip times. Bundles also contain metadata such as an originating timestamp, a useful life indicator, a class of service assignment, and a length indicator to aid in routing and scheduling decisions.
Custody Mechanism – Described in [3], a node is typically responsible for the bundles it carries until they are delivered or transferred to another node. The custody mechanism allows a DTN node to transfer responsibility for bundles to another node, enabling replication, modification, or deletion of the bundles by the new custodian. This is particularly useful when the current node is no longer suitable for forwarding the bundles and only one replica remains.

Early research in vehicular ad hoc networks applied well-known Mobile Ad-Hoc Network routing protocols such as AODV and DSR[9]. These protocols were initially considered due to their applicability in dynamic environments. However, they struggled to perform adequately in VANETs due these protocols insistence on maintaining complete end-to-end paths which is difficult under conditions of frequent topology changes and high maintenance costs [9]. This led to the development of VANET-specific protocols like GPSR relied on assumptions of stableconnections typical of traditional internet protocols[10]. DTNs were introduced to address the shortcomings of traditional network protocols in environments with intermittent connectivity and high latency[3]. The store-carry-forward mechanism central to DTNs allows data packets to be stored temporarily and forwarded opportunistically, ensuring eventual delivery even in the absence of a continuous end-to-end path[2][3]. Protocols such as Epidemic Routing, Spray and Wait and PRoPHET demonstrate DTN strategies and offer varying trade-offs between delivery probability, resource usage and delay[2].
Numerous routing protocols have been proposed in the literature, utilising various different forwarding approaches and replication strategies, each requiring distinct types of information to make forwarding decisions. However only a few operational use cases exist for VANETs with a dominant protocol filling a particular niche nor large-scale implementations have been applied [11][7]. Industrial standards have yet to be sufficiently cohered and owing largely to commercial interests, architecture and protocols are often kept under trade secret[7]. Additionally, while there has been a sustained effort to formalise a benchmark process for VANET simulation it remains a matter of active contention [7][11][9].
VADD –Proposed in [12], VADD uses predictable vehicle mobility constraints of traffic patterns and road layouts in order to choose the next route. Along with this, [12] also proposed several other VADD protocols have been proposed in order to identify the best route for reducing data-delivery delay.
MaxProp – prioritizes packet delivery likelihood and manages storage constraints by discard-ing less probable packets [13]. Authors proposed using VDTN architecture to supply internet access and other services to remote communities. The authors introduce a metric they call “trend of delivery”.
Greedy Perimeter Stateless Routing – (GPSR) is a stateless approach that uses location information to make forwarding decisions, reducing overhead but requiring accurate positioning data [10]. GPSR makes forwarding decisions based on node geography. Initially, GPSR uses a greedy algorithm to forward packets to the neighbor closest to the destination. If greedy forwarding fails if it is not possible to locate a neighbour node that is closer to the packet’s destination than itself. This may happen if the node is geographically closer to the destination than an immediate neighbour. If forwarding fails, the protocol routes packets around the perimeter of the failure area using a right-hand rule until greedy forwarding can resume. GPSR is usually applied to ad-hoc networks [1].
GeoDTN+Nav – proposed in [16] uses direct routing to location when it is available. Oth- erwise, a store-carry-forward approach is employed until a forwarding opportunity arises. It accomplishes this by leveraging GPS data and historic traffic data. By switching between geographic routing and DTN strategies, GeoDTN+Nav is able to retain best-case efficiency in immediate routing scenarios. The purported use-case is urban and highway scenarios.
GeoDTN-NDN – proposed in [17], Geographic data, DTN and is a data retrieval protocol. Data is requested by name across an ad-hoc network and returned using a reverse path.
GeoSpray – [14] uses geographic data to inform routing decisions and store-carry-forward to opportunistically bundle and forward messages. It sends multiple copies that intermediate nodes can clear in order to avoid node spam.
Fastest-ferry routing in DTN-enabled VANET – In [15] FFRDV collects and relays data between disconnected ends and considers the velocity of a given vehicle relative to the final destination in order to improve route times with a purported benefit to emergency services.
Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release – Authors of [20] propose Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release (DBRS- BBR), an improved data transmission approach for VDTNs using the Railway Transport System to address the limitations posed by selfish nodes in traditional schemes. Stationary nodes called Track Side Units with large memory and mobile nodes (trains) with significant buffer capacity are used for message relaying. The proposed Efficient Deterministic Bundle Relaying Scheme with Bulk Bundle Release leverages these nodes to enhance message storage and transfer. A mathematical queuing model and deterministic scheduling are employed to validate this approach. Performance measures such as Mean Queueing Delay, Mean Transit Delay, and Mean End-To-End Delay indicate that DBRS-BBR outperforms the existing Probabilistic Bundle Relaying Scheme.
Routing using Ant Colony Optimization in DTN – [18] proposes a bio-inspired algorithm modeled after the foraging behavior of ants, which can be effectively applied to routing in DTNs. In this approach, nodes in the network leave virtual pheromones on the paths they traverse, similar to ants leaving pheromone trails. These virtual pheromones help guide subsequent data packets along the most promising paths. Over time, pheromone intensity decreases to prevent outdated information from dominating routing decisions and to adapt to changes in network topology. Nodes make forwarding decisions based on the intensity of pheromone trails, with higher pheromone concentrations indicating more reliable and frequently used paths. Heuristic information, such as distance to the destination, node mobility patterns, and encounter histories, is also considered to enhance decision-making. ACO balances exploration and exploitation by occasionally forwarding packets along less-pheromone-rich paths to discover new and potentially better routes, while most packets follow established pheromone trails for reliable and efficient data delivery. Pheromone levels are dynamically updated based on successful deliveries and network conditions, allowing the algorithm to learn and adapt over time.
ACO-based routing can scale well to large and dynamic network environments[18]. It is robust in the face of network topology and node mobility changes due to its adaptive nature, and it finds efficient paths that balance delivery probability and resource usage. However, implementing ACO can be computationally intensive, requiring careful management of pheromone information. In highly dynamic networks, the time required for pheromone information to stabilize can introduce latency, and maintaining and updating pheromone trails across nodes can introduce additional overhead. When compared with Epidemic Routing and PRoPHET, RACOD routing offers higher delivery probability due to the adaptive nature of pheromone trails and heuristic information, lower overhead compared to flooding-based approaches, and improved latency by finding more efficient paths[18].
SecureSIS-DTN – [19] proposes a Service Priority-based Incentive Scheme (SIS), using service priority as an incentive instead of credits. In SIS, nodes that relay more bundles gain higher service priority, improving their bundle delivery ratio. To safeguard against potential attacks on SIS, authors introduce three security measures: signature chains, cooperation fre- quency statistics, and combination clearance. Evaluating SIS using an opportunistic network environment simulator. Results showed that SIS enhances the bundle delivery ratio for honest nodes and effectively curbs selfish behaviors compared to credit-based schemes.
Beyond The Scope – Other areas of interest involve the following. [21] proposed a novel solution involving stratospheric drones to improve data transfer performance of VANETs. [11] identified that although DTNs outperform other VANET routing protocols under conditions of high node density, worst-case performance was only assessed sporadically amongst the literature. Routing involving social metrics is an avenue of future research that fell outside of the scope of this work.

VANETs have shown the capacity to play a central role in critical Smart City (SC) and Intelligent Transport Systems (ITS). My discussion covered various geographic routing protocols in order to expose problems sought solutions. After which, VANET geographic routing research is likely to be a place of increased focus owing in large part to the heuristic nature of geographic route solutions as well as the enthusiasm surrounding Intelligent Transport Systems and Smart City.

[1] S. Sharma, A. Kaul, S. Ahmed, and S. Sharma, “A detailed tutorial survey on vanets: Emerging architectures, applications, security issues, and solutions,” International Journal of Communication Systems, vol. 34, no. 14, e4905, 2021.

[2] A. Hamza-Cherif, K. Boussetta, G. Diaz, and F. Lahfa, “Performance evaluation and comparative study of main VDTN routing protocols under small- and large-scale sce- narios,” Ad Hoc Networks, vol. 81, pp. 122–142, Dec. 2018, ISSN: 1570-8705. DOI: 10.1016/j.adhoc.2018.07.008.

[3] RFC 4838: Delay-Tolerant Networking Architecture, [Online; accessed 24. May. 2024], Jun. 2024. [Online]. Available: https : / / datatracker . ietf . org / doc / html / rfc4838.

[4] RFC 5050: Bundle Protocol Specification, [Online; accessed 24. May. 2024], Jun. 2024. [Online]. Available: https://datatracker.ietf.org/doc/html/rfc5050.

[5] M. S. Hossen, “DTN Routing Protocols on Two Distinct Geographical Regions in an Opportunistic Network: An Analysis,” Wireless Pers. Commun., vol. 108, no. 2, pp. 839– 851, Sep. 2019, ISSN: 1572-834X. DOI: 10.1007/s11277-019-06431-w.

[6] A. M. Abdalla and S. H. Salamah, “Performance Comparison between Delay-Tolerant and Non-Delay-Tolerant Position-Based Routing Protocols in VANETs,” International Journal of Communications, Network and System Sciences, vol. 15, no. 1, pp. 1–14, Jan. 2022. DOI: 10.4236/ijcns.2022.151001.

[7] S. Joerer, C. Sommer, and F. Dressler, “Toward reproducibility and comparability of ivc simulation studies: A literature survey,” IEEE Communications Magazine, vol. 50, no. 10, pp. 82–88, Oct. 2012, ISSN: 1558-1896. DOI: 10.1109/MCOM.2012.6316780.

[8] S. Martínez Tornell, “Delay Tolerant Networks for Efficient Information Harvesting and Distribution in Intelligent Transportation Systems,” Universitat Politècnica de València, Nov. 2020. DOI: 10.4995/Thesis/10251/68486.

[9] L. Rivoirard, M. Wahl, P. Sondi, M. Berbineau, and D. Gruyer, “Performance evaluation of AODV, DSR, GRP and OLSR for VANET with real-world trajectories,” in ITST 2017 - 15th International Conference on ITS Telecommunications, ITST 2017 - 15th International Conference on ITS Telecommunications, Warsaw, POLOGNE, 29-/05/2017 - 31/05/2017, Warsaw, Poland, May 2017, 7p. [Online]. Available: https://hal.science/hal-01556408.

[10] B. Karp and H. Kung, “Gpsr: Greedy perimeter stateless routing for wireless networks,” English, Cited by: 6159; Conference name: 6th Annual International Conference on Mobile Computing and Networking (MOBICOM 2000); Conference date: 6 August 2000 through 11 August 2000; Conference code: 57709, ACM, 2000, pp. 243–254.

[11] A. Torres Amaya, M. S. Fonseca, A. Pohl, and R. Lüders, “Performance assessment of dtn and vanet protocols for transmitting periodic warning messages in high vehicular density networks,” Journal of Communication and Information Systems, vol. 37, no. 1, pp. 91–103, Jun. 2022. DOI: 10.14209/jcis.2022.10.

[12] J. Zhao and G. Cao, “Vadd: Vehicle-assisted data delivery in vehicular ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 57, no. 3, pp. 1910–1922, May 2008, ISSN: 1939-9359. DOI: 10.1109/TVT.2007.901869.

[13] A. Vieira, J. Filho, J. Jr, and A. Patel, “Vdtn-tod: Routing protocol vanet/dtn based on trend of delivery,” Advanced International Conference on Telecommunications, AICT, vol. 2013, pp. 135–141, Jan. 2013.

[14] V. N. Soares, J. J. Rodrigues, and F. Farahmand, “Geospray: A geographic routing protocol for vehicular delay-tolerant networks,” Information Fusion, vol. 15, pp. 102–113, 2014, Special Issue: Resource Constrained Networks, ISSN: 1566-2535. DOI: https: //doi.org/10.1016/j.inffus.2011.11.003.

[15] D. Yu and Y. -B. Ko, “Ffrdv: Fastest-ferry routing in dtn-enabled vehicular ad hoc net- works,” vol. 02, Mar. 2009, pp. 1410–1414.

[16] P.-C. Cheng, K. C. Lee, M. Gerla, and J. Härri, “GeoDTN+Nav: Geographic DTN Routing with Navigator Prediction for Urban Vehicular Environments,” Mobile Netw. Appl., vol. 15, no. 1, pp. 61–82, 2010, ISSN: 1572-8153. DOI: 10.1007/s11036-009-0181-6.

[17] B. Aldahlan and Z. Fei, “A geographic routing strategy with dtn support for vehicular named data networking,” in 2019 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), Aug. 2019, pp. 361–366. DOI: 10.1109/CSE/EUC.2019. 00075.

[18] N. Singh and A. Singh, “RACOD: Routing Using Ant Colony Optimization in DTN,” International Journal of Sensors, Wireless Communications and Control, vol. 10, no. 2, pp. 262–275, 2024. DOI: 10.2174/2210327909666190404141124.

[19] Y. Xie and Y. Zhang, “A secure, service priority-based incentive scheme for delay tolerant networks,” Secur. Commun. Netw., vol. 9, no. 1, pp. 5–18, Jan. 2016, ISSN: 1939-0114. DOI: 10.1002/sec.1372.

[20] P. Kumar Tiwari, S. Prakash, A. Tripathi, et al., “A novel model for vehicular delay tolerant networks using deterministic bundle relaying scheme,” IEEE Access, vol. 12, pp. 68 916–68 925, 2024, ISSN: 2169-3536. DOI: 10.1109/ACCESS.2024.3400408.

[21] V. Kharchenko, A. Grekhov, and V. Kondratiuk, “Traffic modelling in stratospheric drone- assisted VANET,” Peer-to-Peer Networking and Applications, pp. 1–11, Feb. 2024, ISSN: 1936-6450. DOI: 10.1007/s12083-024-01631-z.

I recently had the opportunity to write a programming language in Racket. This was a challenging but rewarding experience, and it taught me a lot about the design and implementation of programming languages.

Static checking is a type of code analysis that is performed on a program’s source code. The goal of static checking is to find errors in the program’s code before the program is run. Static checking can be used to find a variety of errors, including:

• Type errors: These errors occur when a variable is assigned a value of the wrong type.
• Semantic errors: These errors occur when the program’s code does not make sense semantically. For example, a semantic error could occur if a function is called with the wrong number of arguments.
• Logical errors: These errors occur when the program’s code does not do what it is supposed to do. For example, a logical error could occur if a loop is infinite. Part of a programming languages definition is what kind of static checking is done before code evaluation can be performed. Notice the implication here, all programming languages to some degree do static type checking, static type checking itself refers to anything that is done to reject a program before it runs.

The Importance of Concrete and Abstract Syntax In many programming languages, there is a distinction between concrete syntax and abstract syntax. Concrete syntax is the way that programs are written in human-readable form. Abstract syntax is the internal representation of programs that is used by the compiler or interpreter.

The distinction between concrete and abstract syntax allows for a separation of concerns. The concrete syntax can be designed to be easy for humans to read and write, while the abstract syntax can be designed to be efficient for computers to parse and execute.

Racket is a programming language that makes a distinction between concrete and abstract syntax. In Racket, programs are written in a concrete syntax that is based on the Scheme programming language. However, the abstract syntax of Racket programs is represented using a data structure called a struct.

The use of structs to represent the abstract syntax of Racket programs has several advantages. First, it makes it easy to define the semantics of Racket programs. The semantics of a program can be defined by simply specifying the operations that are performed on the structs that represent the program’s abstract syntax.

Second, the use of structs makes it easy to implement a compiler or interpreter for Racket. The compiler or interpreter can simply parse the concrete syntax of a Racket program and then construct the corresponding structs that represent the program’s abstract syntax.

Finally, the use of structs makes it easy to implement extensions to Racket. New features can be added to Racket by simply defining new structs that represent the new features.

The use of concrete and abstract syntax is a powerful tool that can be used to improve the design of programming languages. Racket is a good example of a language that makes extensive use of this technique.

In Racket, Scheme, LISP, Javascript, Ruby and countless other languages, something called an eval receives a list of concrete syntax that it then has to parse and then run. Racket’s approach of having the concrete and abstract syntax is extreme convenient to anyone that wants to implement their own programming language.

Racket as a Metaprogramming Platform

Racket is a powerful programming language that can be used to create other programming languages. This is because Racket has a well-defined abstract syntax, and it provides a number of features that make it easy to create new languages.

One of the key features of Racket that makes it a good metaprogramming platform is the eval function. The eval function takes a list of expressions and evaluates them. This means that we can write functions that return lists of expressions, and then use the eval function to evaluate those expressions.

This makes it possible to create new programming languages by defining new syntactic forms and then using the eval function to evaluate expressions that use those new syntactic forms.

Another key feature of Racket that makes it a good metaprogramming platform is the fact that every Racket file is its own programming language. This is because every Racket file through function and procedure definitions expands the semantics its own file and any file connected to it. The language is essentially compose of Racket files calling other Racket files, the injection of “definition-meanings” is called macro expansion.

• Macro expansion is a process that replaces a macro call with the body of the macro. The body of the macro is a function that is evaluated to produce the desired output.
• define-syntax is a function that defines a new macro. The macro definition takes two arguments: the name of the macro and the body of the macro.

The two concepts are similar because they both allow you to define new syntactic forms. However, there are some important differences between them.

• Macro expansion is performed automatically by the compiler or interpreter. This means that you do not need to explicitly call the macroexpand function to expand a macro.
• define-syntax is a function that you have to call explicitly. This means that you have more control over when and how the macro is expanded.

Here is an example of how macro expansion and define-syntax can be used to define a new syntactic form:

(define-syntax if
  (lambda (x y z)
    (if (eval x)
      y
      z)))

(if (> 1 0)
  "greater than"
  "less than or equal to")

In this example, the if macro is defined to take three arguments: the condition, the then-clause, and the else-clause. The macro expansion of the if macro is a function that takes the three arguments and returns the appropriate value.

The define-syntax function is used to define the if macro. The first argument to define-syntax is the name of the macro, which is if in this case. The second argument to define-syntax is the body of the macro, which is the function that is evaluated to produce the desired output.

MUPL Syntax

MUPL programs are written directly in Racket by using the constructors defined by the structs defined at the beginning of our file. The syntax for MUPL is as follows:

• If s is a Racket string, then (var s) is a MUPL expression (a variable use).
• If n is a Racket integer, then (int n) is a MUPL expression (a constant).
• If e1 and e2 are MUPL expressions, then (add e1 e2) is a MUPL expression (an addition).
• If s1 and s2 are Racket strings and e is a MUPL expression, then (fun s1 s2 e) is a MUPL expression (a function). In e, s1 is bound to the function itself (for recursion) and s2 is bound to the (one) argument. Also, (fun #f s2 e) is allowed for anonymous nonrecursive functions.
• If e1, e2, and e3, and e4 are MUPL expressions, then (ifgreater e1 e2 e3 e4) is a MUPL expression. It is a conditional where the result is e3 if e1 is strictly greater than e2 else the result is e4. Only one of e3 and e4 is evaluated.
• If e1 and e2 are MUPL expressions, then (call e1 e2) is a MUPL expression (a function call).
• If s is a Racket string and e1 and e2 are MUPL expressions, then (mlet s e1 e2) is a MUPL expression (a let expression where the value resulting e1 is bound to s in the evaluation of e2).
• If e1 and e2 are MUPL expressions, then (apair e1 e2) is a MUPL expression (a pair-creator).
• If e1 is a MUPL expression, then (fst e1) is a MUPL expression (getting the first part of a pair).
• If e1 is a MUPL expression, then (snd e1) is a MUPL expression (getting the second part of a pair).
• (aunit) is a MUPL expression (holding no data, much like () in ML or null in Racket). Notice (aunit) is a MUPL expression, but aunit is not.
• If e1 is a MUPL expression, then (isaunit e1) is a MUPL expression (testing for (aunit)).
• (closure env f ) is a MUPL value where f is mupl function (an expression made from fun) and env is an environment mapping variables to values. Closures do not appear in source programs; they result from evaluating functions.

One of the things that I learned is that it is important to have a clear understanding of the goals of the language before you start writing it. In my case, I wanted to create a simple language that would be easy to understand. I also wanted to create a language that would be expressive and powerful.

Another thing that I learned is that it is important to have a good design for the language. This includes things like the syntax, the semantics, and the libraries that are provided with the language. I spent a lot of time thinking about these things, and I think that the design of MUPL is pretty good.

Of course, no language is perfect, and there are always things that could be improved. However, I am happy with the way that MUPL turned out, and I think that it is a good learning experience for anyone who is interested in the design and implementation of programming languages.

Here are some personal reflections on the experience of writing MUPL in Racket:

• Racket is a great language for writing programming languages. The Racket syntax is very clean and concise, and the Racket environment provides a lot of tools that make it easy to write and test code.
• Writing a programming language is a lot of work. There are a lot of things to think about, such as the syntax, the semantics, the libraries, and the implementation. It takes a lot of time and effort to get everything right.
• It is rewarding to create something new. It was satisfying to see MUPL come together, and it was even more satisfying to see other people using it and learning from it.

I am grateful for the opportunity to have written MUPL and the excellent class Programming Languages Part B. I am excited to see what the future holds for my implementation of MUPL. I hope that MUPL will continue to be used and learned by people all over the world :-).

Some notes from my reading of Harold Abelson’s EXCELLENT lecture in the famous MIT course Structure and Interpretation of Computer Programs.

The subject matter … involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. ese processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. ey are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcraed discrete collections ofsymbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately aains a metastable place within still another model with which we struggle. e source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs! (xii-xiv, Structure and Interpretation of Computer Programs)

Many people think that computer science is all about computers. They think that it’s about programming, hardware, and software. But this is not really true. Computer science is actually about problem solving. It’s about finding ways to solve problems using computers.

In the same way that geometry is not really about surveying instruments, computer science is not really about computers. Geometry is about the properties of space and shapes. It’s about finding ways to measure and describe these properties. Computer science is about the properties of computation. It’s about finding ways to solve problems using computers.

The tools of computer science are computers. But the essence of computer science is problem solving. It’s about using the power of computers to solve problems that would be difficult or impossible to solve by hand.

This is why computer science is such a powerful tool. It can be used to solve problems in a wide variety of fields, from science to engineering to business. And as computers become more powerful, the possibilities for computer science become even greater. If you’re interested in problem solving, then computer science is the field for you. It’s a field that’s constantly evolving, and it’s a field that offers endless possibilities.

In computer science, there are two main types of knowledge: declarative and imperative. Declarative knowledge is knowledge about what is true. It makes statements of fact that can be used to reason about things. For example, the statement “the square root of 16 is 4” is a declarative statement.

Imperative knowledge, on the other hand, is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal. For example, the statement “to find the square root of a number, you can use the Babylonian method” is an imperative statement.

Declarative knowledge is often expressed in the form of axioms, which are statements that are assumed to be true. Imperative knowledge is often expressed in the form of algorithms, which are step-by-step procedures for solving problems.

Computer science is concerned with both declarative and imperative knowledge. Declarative knowledge is used to represent the structure of data and the relationships between different pieces of data. Imperative knowledge is used to describe how to manipulate data and solve problems.

In computer science, we focus on imperative knowledge. This is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal.

An algorithm is a step-by-step procedure for solving a problem. It is a precise description of what to do in order to get the desired result. Algorithms are often used in computer programs to automate tasks.

A procedure is a type of algorithm that is specifically designed to be used by computers. Procedures are typically written in a programming language, which is a language that computers can understand.

Declarative knowledge is knowledge about what is true. It makes statements of fact that can be used to reason about things. For example, the statement “the square root of 16 is 4” is a declarative statement.

Imperative knowledge, on the other hand, is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal. For example, the statement “to find the square root of a number, you can use the Babylonian method” is an imperative statement.

The main difference between declarative and imperative knowledge is that declarative knowledge is about what is true, while imperative knowledge is about how to do something.

We care about imperative knowledge because it allows us to give computers instructions on how to solve problems. Computers are machines that can only follow instructions, so we need to give them instructions in a way that they can understand.

Algorithms are a way of expressing imperative knowledge in a way that computers can understand. By writing algorithms, we can give computers instructions on how to solve a wide variety of problems.

The Importance of Procedures

Procedures are an important type of algorithm because they are specifically designed to be used by computers. Procedures are typically written in a programming language, which is a language that computers can understand.

This makes procedures a very convenient way to give computers instructions. We can simply write the procedure in a programming language, and then the computer can follow the instructions to solve the problem.

Procedures and Processes

A procedure is a step-by-step description of how to do something. It is a recipe for achieving a goal.

A process is the actual sequence of steps that are carried out by a computer when it is executing a procedure.

When we want to get the computer to actually compute a value, we will evaluate an expression that applies a procedure to some values. The process is the sequence of steps that the computer takes to evaluate the expression and produce the desired value.

The focus of this course is on understanding how to control different kinds of processes by describing them with procedures.

There are two main ways to control processes:

• Sequential control is the most basic way to control processes. In sequential control, the steps in a process are executed one after the other, in a linear fashion.
• Conditional control allows us to specify that certain steps in a process should only be executed if certain conditions are met. This allows us to create more complex processes that can respond to different situations.

Processes are an essential part of computer programming. They allow us to give computers instructions on how to solve problems. By understanding how to control processes, we can create programs that can perform complex tasks.

A computational process is an abstract being that inhabits computers. It is a sequence of steps that are carried out by the computer to achieve a goal.

The evolution of a process is directed by a pattern of rules called a program. Programs are written by people to tell the computer what to do.

Computational processes are like sorcerer’s spirits. They cannot be seen or touched, but they are very real. They can perform intellectual work, answer questions, and affect the world.

The programs we use to conjure processes are like sorcerer’s spells. They are carefully composed from symbolic expressions in programming languages.

When a computational process is executed on a correctly working computer, it executes the program precisely and accurately. This means that even small errors in programs can have complex and unanticipated consequences.

Learning to program is not as dangerous as learning sorcery, but it still requires care, expertise, and wisdom. A small bug in a computer-aided design program, for example, could lead to the catastrophic collapse of an airplane or a dam.

Master software engineers have the ability to organize programs so that they can be reasonably sure that the resulting processes will perform the tasks intended. They can visualize the behavior of their systems in advance, and they know how to structure programs so that unanticipated problems do not lead to catastrophic consequences.

Well-designed computational systems, like well-designed automobiles or nuclear reactors, are designed in a modular manner, so that the parts can be constructed, replaced, and debugged separately.

Large systems are often complex and difficult to understand. This is because they are made up of many different parts that interact with each other in complex ways.

The language of procedures and processes can help us to control complexity in large systems by providing a way to describe the different parts of the system and how they interact with each other. This allows us to understand the system better and to design solutions that are more likely to be successful.

By abstracting existing procedures to see how they have been used to solve problems. This will help us to understand how the language of procedures and processes can be used in practice. We will also spend some time designing our own procedures to solve problems. This will give us the opportunity to practice using the language of procedures and processes and to see how it can be used to control complexity in large systems.

*Abstract mathematical concepts can be a challenge for many undergraduate computer science learners.** Some of the most common areas of difficulty include self-similarity, parametric types and reasoning about types, recursion, recursive thinking, recursive data types, graphs, trees, cases, pattern matching, and using logic and reasoning about code.

Even after successfully completing a hard recursion exercise or course, some learners may still feel like they don’t fully understand the concepts involved.** This can be frustrating and discouraging, and it can lead to feelings of inadequacy or a desire to skip future courses that involve abstract mathematical concepts.

• “I’ve done the How to Code courses, but I don’t know if they worked out for me.”
• “I got a ‘All 20 test passed!’, so thanks! I do still have difficulty understanding what I did exactly…”
• “I’ve made it this far (to PLB), I’ve spent months but I’m not improving at all.”
• “I’m so tired of getting stuck on each problem for hours. I just want to move on.” (hey I’ve been there!)
• “I’m just gonna get through this material quickly, or skip it if it takes too much time.”
• “Who cares about these languages anyway? Why should I even use recursion? I’m not convinced.”
• “After all this SML/Racket crap, …”
• i did do htc but i struggled with it a lot, i didnt want to waste time so i moved on with intent to revisit it, i saw how valuable the course was…
• “this class almost made me quit OSSU after i forced myself to do the first part, so i skipped the second one”
• I’ve been stuck on this course for so long, I’ve read the comments and I understand it should be done but I really can’t focus on it. I tried using the book instead too, but it feels like dragging myself through mud.
• Every time I tried to think about all the steps in a list with more than 2 items, my head just explode.
• With more simple problems I can imagine all the calls and the stack being built and returning values, but for this problem in particular, no way! its normal or I am missing something? See here for context

Open Source Society University (OSSU) is a self-paced, open-source curriculum for computer science education and community of learners. The curriculum is designed to provide a comprehensive and well-rounded grounding in the fundamental concepts of computer science. The OSSU curriculum is based on the degree requirements of undergraduate computer science majors, but it does not include general education requirements. This is because it is assumed that most learners will already have a foundation in these subjects.

OSSU is more than just a curriculum. It is also a community of self-learners. The community is organized on Discord, where learners connect with each other, ask questions, and get help. It is an excellent resource for learners who are struggling with a particular concept or who are looking for advice on how to approach a problem, in or outside of the curriculum. The discord provides a place for find study groups and to connect with other learners who are interested in CS or related topics and is run mostly by learners themselves in a generally very welcoming and supportive manner.

On the OSSU discord, it has become commonplace to hear students complain about the first two core CS subjects (How To Code: Simple Data and How To Code: Complex Data). A key complaint relates to learners struggles with recursion, recursive data types, and reasoning about code. This difficulty is not limited to the OSSU curriculum, but is a common problem in computer science education. Some learners report feeling like they are not making progress, or that they do not understand what they are doing correctly. They may also repeat mistakes or exhibit misunderstandings that they had in previous courses.

This difficulty can be attributed to a lack of exposure to the underlying abstract mathematical concepts, such as logic, proofs, reasoning, induction, recursive definitions, and structural induction. These concepts are often not taught in high school, and as a result, learners may not have the foundation they need to understand recursion. In addition, the languages used in these OSSU courses, Racket and SML, can be difficult for learners who are not familiar with them. These languages use a lot of parentheses and have a different syntax than many other programming languages. This can make it difficult for learners to understand the code and to reason about how it works. The OSSU courses do a good job of teaching the concepts of recursion and recursive data types. However, it has been argued that the curriculum could do more to prepare learners for the mathematical concepts that are necessary to understand recursion.

This problem and a novel solution for the OSSU context was proposed here. In sum, it was argued that there is a strong overlap between the topics covered in Mathematics for Computer Science (MCS, offered by MIT, in the OSSU core maths curriculum) and the concepts that learners struggle with in the Core Programming courses. For example, both Unit 1 of MCS and the Core Programming courses cover recursion, recursive data types, cases, and pattern matching. By requiring Unit 1 of MCS as a prerequisite, learners would be better prepared to understand these concepts when they encounter them in the Core Programming courses. I would like to outline and propose an alternative perspective and possible solution. In my next post I will rehearse a perspective on computer science grounded in a theory-first approach to the topic relevant to learners experience.

1. https://ieeexplore.ieee.org/document/8068262
2. https://vtechworks.lib.vt.edu/handle/10919/64249
3. The post will provide an overview and hopefully some way approach consistently recurrent issue in computer-science pedagogy.
4. This was first raised here [https://github.com/ossu/computer-science/issues/1094]

The mere mention of the name freedom my heart opens and flowers, and with the word necessity, it contracts painfully. For I feel that I am free, and I hate the thought that I am not so. (Fichte Foundations of Natural Right 1796)

Fichte’s concept of freedom founders on the notion of the individual ego, his own. Hegel notes Fichte being “depressed” by the “hideous order” and “unbreakable symmetry” of the natural world. Fichte saw freedom as a way of escaping from the deterministic laws of nature.

Fichte, however, was not satisfied with this. He felt gloom, horror, and abhorrence at the mere thought of the eternal laws of nature and their strict necessity. He felt that they were something foreign to him, and that he was not at home in them. (Hegel Lectures on the History of Philosophy 1830) —

Fichte’s philosophy was a major influence on the Romantic movement. He argued that knowledge is not a passive state of mind, but rather an active process of creation. This idea was central to the Romantics’ belief that the individual is capable of transforming the world through their own creative activity.

Fichte also emphasized the importance of action in the pursuit of freedom. He argued that freedom is not something that can be achieved through contemplation, but rather through constant striving and engagement with the world.

If you are simply contemplative being, and ask for the answer to what to do or how to live in the realm of knowledge you will never discover an answer simply because knowledge always presupposes some larger knowledge. At best you might end with some like Spinoza’s system where there is a rigid logical unity in which there is no room for movement. (Fichte Science of Knowledge 1794)

Our lives do not depend on contemplative knowledge. Life doesn’t begin with disinterested contemplation of nature. Life begins with action. Action is the first and fundamental condition of all knowledge. (Fichte The Vocation of Man 1794)

The double-edged nature of freedom

Things are what they are not because they are what they are but because I make them so. They depend upon the way in which I treat them, what I need them for. (Fichte Science of Knowledge 1794)

Fichte’s claim is that our lives do not depend on contemplative knowledge. Life doesn’t begin with disinterested contemplation of nature. Life begins with action. Knowledge is an instrument for an affective life of action. Knowledge is knowing how to be, knowing what to do etc. knowing how to live and what to do in order not to perish. This knowledge as arbitrary acceptance some part of the world, as the aspects presupposed by the biological urge in the necessity of living - is for Fichte an act of faith.

“We do not act because we know, we know because we are called upon to act. Knowledge is not a passive state. External nature impinges upon us and stops us. In it’s clay of our creation we have freedom again.” “things are what they are not because they are what they are but because I make them so”. “Things depend upon the way in which I treat them, what I need them for”.

Food is not what I hunger for, it is made food by my hunger. I do not hunger for food because it is laid beside me, the object becomes food. I do not accept what nature offers because I must, I don’t simply register what occurs like a machine, I believe it because I will. Who is master, nature or I? I am not determined by ends, ends are determined by me. “The world is a poem dreamt out in my inner life”. Experience is something which I determine because I act. Robins are romantic because I make them romantic, nothing is romantic in nature. 

But freedom is double edge. Because I am free I am able to exterminate others.

Savages exterminate each other, and civilized nations, using the power of law, unity, and culture, will go on exterminating each other. Culture is not a deterrent of violence. (Fichte Addresses to the German Nation 1807)   The statement comes in contradiction with a united 18th century idea, that culture was a deterrent of violence, because culture is knowledge, and knowledge proves the ‘inadvisability’ of violence.

The world cannot be half slave and half free. If we are a free nation, if we are great creators engaged in creating those great values which in fact history has imposed on us since we happen not to have been corrupted by the great decadence which has fallen upon the Latin nations. Germany happens to be in some sense healthier and more vigorous if perhaps more barbarous than those decadent peoples who are nothing but the debris of what was once no doubt a very respectable roman civilization, if that is what we are then we must be free no matter what the cost. Since the world cannot be half slave and half free we must conquer the others and absorb them into our texture. (Fichte Addresses to the German Nation 1807)

Fichte’s philosophy was eventually used to justify German nationalism. He argued that the German nation was a unique and superior entity that had a special destiny to fulfill. He also argued that the German nation had a right to expand and conquer other nations.

Here lies the quite difficult problem in Fichte’s worldview, how to square his defence of German colonialism and his romanticism. That only contravention of violence was some higher moral regeneration. “Man shall be and do something.” For Fichte man is a ‘continuous action’. He must constantly create. A man who accepts what nature gives him is dead. This was equally applicable to human beings and of nations.  The thread that Fichte follows to end up with a justification of colonialism, Individuals become Free Individuals, but they cannot become free while they are an object in space because of nature’s unbreakable limitations on the object (gravity, time, transcendental etc), therefore the free being is larger than man, the body is cast off in favour of spirit. Spirit is not the spirit of the individual, it is common to many men because each individual spirit is imperfect, it is confined by the particular bodily form, then it becomes pure spirit as some mystical entity, like God, in which we are all sparks of its central fire, and here it ends in a kind mysticism.  Once nationalist sentiment in Germany had risen, Fichte began to confer with Handel arguing that ‘man is made a man by other men’, by language, education, culture etc. inventions of others. Man is an element of this common stream and man is in an organic unity with other men. This marked the movement from the individual, as an empirical unit in space to the individual as something larger, a nation, a class, a sect, etc. This movement implies a transition on every level. Man is necessity of action because it’s necessity of action (circular). A nation’s necessity to be free means it to be free of other nations and if other nations obstruct it it must make war.

Metacritique is a term used to describe the process of critically examining the underlying assumptions of a philosophical system. It is often used in the context of postmodern thought, but it has a much longer history.

The term “metacritique” was first used by the German philosopher Johann Georg Hamann in the late 18th century. Hamann argued that each generation of philosophers must critically examine the metaphysical framework of their parents. He believed that this was necessary in order to avoid simply repeating the mistakes of the past.

Hamann’s metacritique of Kant was particularly influential. He argued that Kant’s critical philosophy was based on a number of assumptions that were ultimately untenable. For example, he argued that Kant’s distinction between the phenomenal and noumenal worlds was arbitrary and ultimately meaningless.

The idea of metacritique has been a recurring theme in the history of philosophy. In addition to Hamann, other philosophers who have engaged in what could be termed “metacritique” include Hegel, the young Hegelians, Marx, the Frankfurt School, and Habermas.

Hegel’s Science of Logic is a classic example of a metacritique. In this work, Hegel argues that the history of philosophy is a process of progressive self-understanding. He shows how each major philosophical system contains within it the seeds of its own destruction.

The young Hegelians and Marx were also engaged in metacritique. They argued that Hegel’s system was ultimately flawed because it did not adequately account for the material conditions of existence. They developed their own metacritiques of Hegel, which emphasized the importance of history and class struggle.

The Frankfurt School also engaged in metacritique. They adopted parts of Hegel’s method, but they supplemented it with psychoanalysis. They argued that Hegel’s method could be used to analyze the unconscious forces that shape human society.

Habermas has also engaged in metacritique. He has argued that the history of philosophy can be seen as a process of rationalization. He has also developed his own metacritique of the entire tradition, which accepts Kant, Darwin, and other key figures.

Habermas’s intersubjective framework is a way of understanding the relationship between the individual and society. It is based on the idea that knowledge is always socially mediated. This means that our understanding of the world is shaped by the language and culture that we are embedded in.

Habermas’s intersubjective framework has been influential in a number of fields, including philosophy, sociology, and political theory. It has been used to analyze a wide range of issues, including the nature of communication, the relationship between power and knowledge, and the possibility of social change.